Алгоритм Мо (кит. 莫隊算法) вероятно не был открыт, но точно был популяризован китайским спортивным программистом Мо Тао (莫涛) и его сокомандниками в конце нулевых годов.
Он позволяет в оффлайн отвечать на самые разные запросы на подотрезках, которые часто невозможно решить даже самыми продвинутыми структурами данных.
Для примера рассмотрим такую задачу: дан массив размера $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}})$, что доказывается аналогично исходному алгоритму.