Алгоритм Мо - Алгоритмика
Алгоритм Мо

Алгоритм Мо

автор Сергей Слотин
пререквизиты Корневые эвристики

Алгоритм Мо (кит. 莫隊算法) вероятно не был открыт, но точно был популяризован китайским спортивным программистом Мо Тао (莫涛) и его сокомандниками в конце нулевых годов.

Он позволяет в оффлайн отвечать на самые разные запросы на подотрезках, которые часто невозможно решить даже самыми продвинутыми структурами данных.

Для примера рассмотрим такую задачу: дан массив размера $n$ целых чисел от $1$ до $n$, и требуется отвечать на $q$ заранее известных запросов «количество различных чисел на отрезке $[l_i, r_i]$».

Алгоритм

Если корневая эвристика по запросам группирует запросы по временным признакам, то алгоритм Мо — по пространственным.

Сгруппируем все запросы в блоки размера $c \approx \sqrt n$ по их левой границе и внутри каждого блока отсортируем запросы по правой границе:

// границы и номер запроса, на который нужно ответить
struct query { int l, r, idx; };

int a[maxn], ans[maxq]; // исходный массив и массив ответов на запросы
vector<query> b[c];


// где-то в main:

for (query q : queries)
    b[q.l / c].push_back(q);

for (int i = 0; i < c; i++) {
    sort(b[i].begin(), b[i].end(), [](query a, query b){
        return a.r < b.r;
    });
}

Будем обрабатывать каждый такой блок запросов по отдельности, заведя следующие переменные:

  • границы $[l, r]$ текущего отрезка (изначально пустого: $l = i \cdot c$ и $r = i \cdot c - 1$);
  • массив cnt, размера $n$, в котором для каждого значения хранится число элементов на текущем отрезке с данным значением (изначально заполнен нулями);
  • переменная res, равная числу различных элементов на текущем отрезков, то есть числу ненулевых элементов массива cnt (изначально ноль).

Массив cnt и переменную res легко пересчитать за $O(1)$ при расширении или сжатии границ на единицу:

int cnt[maxn];
int res;

void add(int k) {
    if (cnt[a[k]]++ == 0)
        res++;
}

void del(int k) {
    if (--cnt[a[k]] == 0)
        res--;
}

Будем медленно двигать границы влево и вправо таким образом, чтобы текущий отрезок в какой-то момент времени был равен каждому отрезку-запросу, и в этот момент времени мы ответим на запрос, записав res в нужную ячейку массива ответов ans.

А именно, будем двигать правую границу текущего отрезка, пока она не станет равной правой границе очередного запроса (они отсортированы по правой границе), а затем будем двигать левую границу вправо или влево, пока она не совпадет с его левой границей:

for (int i = 0; i < c; i++) {
    // обнуляем переменные
    int l = i * c, r = i * c - 1;
    memset(cnt, 0, sizeof cnt);
    res = 0;
    for (query q : b[i]) {
        // пока правая граница не дошла до границы запроса
        while (r < q.r)
            add(++r);
        // дальше делаем так, чтобы левая граница совпала
        while (l < q.l)
            del(l++);
        while (l > q.l)
            add(--l);
        ans[q.idx] = res;
    }
}

Трюк в том, что правая граница суммарно сдвинется на $O(n)$, потому что отрезки отсортированы, а левая каждый раз сдвинется не более чем на $O(\sqrt n)$, так как все левые границы сгруппированы по корневым блокам. Изменение левых границ суммарно по всем блокам займёт $O(q \sqrt n)$ операций, а правых $O(n \sqrt n)$, так что итоговая асимптотика решения будет $O(q \sqrt n + n \sqrt n)$.

Вариации

Задача. Требуется находить наиболее часто встречающийся элемент на отрезке.

Можно так же поддерживать массив cnt, и ещё помимо него вспомогательную внутреннюю структуру, в которой можно упорядоченно хранить пары (встречаемость, элемент) и доставать максимум. Для этого можно использовать двоичные структуры вроде set, хотя это добавит лишний логарифм в асимптотику.

Чтобы решить задачу за чистый $O(n \sqrt n)$, можно в качестве внутренней структуры завести массив двусвязных списков (встречаемость элемента → какие элементы имеют такую встречаемость), а также массив указателей-итераторов — для каждого элемента, где и в каком списке он сейчас находится. Тогда при добавлении / удалении элемента нужно его удалить из его текущего списка и вставить в более верхний / нижний, а при ответе на запрос просто взять какой-нибудь элемент из самого верхнего непустого списка.

Решение можно упростить, обойдясь без структур вообще: будем поддерживать только массив cnt и сам ответ res (количество самого частого элемента), но при этом последний будем релаксировать только при добавлении элементов, а при удалении ничего делать не будем:

void add(int k) {
    res = max(res, ++cnt[a[k]]);
}

void del(int k) {
    cnt[a[k]]--;
    // res тут не обновляется
}

Теперь в основной процедуре при откатывании левой границы будем откатывать res, просто запомнив его значение до обработки запроса (до начала расширения левой границы):

for (int i = 0; i < c; i++) {
    int l = i * c, r = i * c - 1;
    memset(cnt, 0, sizeof cnt);
    res = 0;
    for (query q : b[i]) {
        while (r < q.r)
            add(++r);
        int backup = res;
        while (l < q.l)
            del(l++);
        ans[q.idx] = res;
        while (l > q.l)
            add(--l);
        res = backup;
    }
}

Задача. Требуется находить $k$-ую порядковую статистику на отрезке.

Можно хранить все числа из запроса в декартовом или любом другом дереве — например дереве отрезков для суммы или даже дереве Фенвика — и обновлять его и делать по нему спуск за $O(\log n)$.

Чтобы избавиться от логарифма, неожиданно можно использовать корневую декомпозицию как внутреннюю структуру. Нужно сжать все числа в промежуток $1$ до $n$, завести массив «сколько раз встречается число $x$» и поддерживать сумму для каждого его корневого блока. При обновлении нужно сделать $\pm 1$ ровно в двух ячейках за $O(1)$, а при запросе $k$-той порядковой статистики пройтись сначала по $O(\sqrt n)$ блокам, а потом по $O(\sqrt n)$ элементам внутри одного блока.

Так как запросов обновления во внутренней структуре в $O(n \sqrt n)$, а запросов чтения всего $O(n)$, то асимптотика $O(\sqrt n)$ на вторые ни на что не повлияет. Это довольно редкая ситуация, когда корневая оптимизации асимптотически побеждает дерево для ровно той же задачи — внутри другой корневой оптимизации.

На деревьях. В некоторых задачах требуется считать результаты операций на путях в дереве. Например: рядом с каждой вершиной есть число, и нужно возвращать количества различных значений на путях.

Идея примерно такая же, как при сведении LCA к RMQ: если выписать эйлеров обход дерева (каждую вершину дважды), то задача сводится к задаче на массиве, только с одним исключением — мы должны добавлять в структуру только те элементы, которые содержатся на отрезке ровно 1 раз.

Подробнее можно почитать в статье про запросы на деревьях.

«3D Мо». Если очень захотеть, этот подход можно применять и в задачах, где надо обрабатывать запросы обновления. Для этого нужно ввести третий параметр get-запроса $t$, который будет равен числу update-запросов до текущего get («время»).

Снова отсортируем все get-запросы, но на этот раз в порядке

$$ \left(\lfloor \frac{t}{n^{\frac 2 3}} \rfloor, \lfloor \frac{l}{n ^{\frac{2}{3}}} \rfloor, r\right) $$

и обработаем их таким же алгоритмом, только в трёх измерениях.

Единственный нюанс — теперь при переключении между версиями массива надо будет менять ровно один элемент, и иногда менять его в структуре, если он принадлежал текущему отрезку.

Время работы такого подхода будет $O(n^{\frac{5}{3}})$, что доказывается аналогично исходному алгоритму.