Любая структура, будь то дерево отрезков или разреженные таблицы, имеет некоторые ограничения на функции, которые она должна считать на отрезке. Алгоритм Мо решает огромное количество задач запросов на отрезке в оффлайн.
Пускай надо отвечать на запросы суммы на отрезке. Сделаем вид, что мы не знаем ни про какие структуры на отрезке. Запросов изменений пока нет.
Давайте будем онлайн хранить структуру, умеюшая выполнять операции: добавить элемент в структуру, удалить элемент из структуры, посчитать ответ.
Будем поддерживать отрезок \([l;r]\), на котором сейчас хранится ответ. Когда приходит запрос \([l_i,r_i]\), двигаем наши указатели, чтобы в структуре хранился именно этот отрезок и запрашиваем сумму.
Очевидно, что легко сконструировать случаи, когда алгоритм будет работать за квадрат. Давайте используем тот факт, что запросы все в оффлайне и как-нибудь по-хорошему посортим наши запросы.
Итак, отсортируем все запросы по левой границе (при одинаковой левой - по возрастанию правой). Разобьем все запросы на \(\sqrt{q}\) блоков по \(\sqrt{q}\) запросов в каждом. Внутри блоков отсортируем запросы по возрастанию правой границы. Неплохое ускорение дает, если в четных блоках мы будем сортировать по убыванию правой границы, а в нечетных - по убыванию.
Тогда внутри одного блока мы будем не очень сильно двигать границы. Можно доказать, что всего указатели будут двигаться \(O((n+q)\sqrt{n})\).
Пускай надо отвечать на запросы MEX на отрезке. Можно использовать сет, чтобы хранить, каких элементов сейчас нет в структуре. Но тогда добавляется лишний логарифм. Давайте заметим, что нам надо быстро удалять и добавлять число в структуру, а отвечать на запросы надо всего \(q\) раз. Тогда заведем корневую на отрезке и будем для каждого блока хранить сколько уникальных чисел там содержится. Если в блоке присутствуют все числа, то его можно смело пропускать. Обновлять такую корневую можно за \(O(1)\), зато запросы делать за \(O(\sqrt{n})\). Асимптотика останется той же.
Пускай даны еще и запросы на обновления. Тогда у нас не 2 измерения (\(l\) и \(r\)), а 3 - добавляется \(t\) - измерение запросов изменения. Посортируем похожим образом - только будем разбивать блоки по \(n^\frac{2}{3}\).
Когда меняем координату \(t\) посмотрим где произошло изменение - если это измение попадает на нашу структуру, то необходимо скорректировать ее.
Вообще, чтобы реализация была проще можно написать компаратор сравнивающий пары чисел (если это обычный Мо) или тройки (если 3Д).
Пускай дано дерево, покажем, что любые запросы на путях дерева можно свести к запросам на путях дерева. Выпишем эйлеров обход дерева. Рассмотрим отрезок \([tin_u;tout_v]\). Заметим что эйлеров обход на этом отрезке содержит вершины на пути между \(u\) и \(v\) нечетное количество раз, остальные вершины - четное. Тогда напишем обычный Мо, который работает на отрезках, только будем учитывать лишь те вершины/ребра встречающиеся четное количество раз.