Алгоритм Мо: запросы на отрезках оффлайн за O((n+q)√n)
Алгоритм Мо простыми словами: как отсортировать запросы по блокам, двигать два указателя и считать число различных элементов на отрезке за O((n+q)√n). Код на Python и JS.
Коротко
| Что | Значение |
|---|---|
| Задача | Ответить на запросов вида «посчитай что-то на отрезке » |
| Условие | Все запросы известны заранее (оффлайн), массив не меняется |
| Главная идея | Переставить запросы так, чтобы окно двигалось мало |
| Сортировка | По блоку , внутри блока — по |
| Сложность | вызовов add/remove + на сортировку |
| Что нужно уметь | Добавить элемент в окно и убрать его за |
Алгоритм Мо — это скользящее окно, которое прыгает не слева направо, а между заранее отсортированными запросами. Он не требует ни дерева отрезков, ни ассоциативной операции: достаточно уметь поддерживать ответ при добавлении и удалении одного элемента.
Задача: число различных элементов на отрезке
Дан массив a длины и запросов . Для каждого нужно сказать, сколько различных чисел лежит в a[l..r].
a = [1, 2, 1, 3, 2, 2, 4, 1]
(0, 3) → {1, 2, 3} → 3
(2, 5) → {1, 3, 2} → 3
(1, 6) → {2, 1, 3, 4} → 4
(0, 7) → {1, 2, 3, 4} → 4
(4, 4) → {2} → 1
Почему не взять дерево отрезков? Потому что «число различных» не складывается: если слева 3 различных, а справа 2, на всём отрезке может оказаться и 3, и 5 — зависит от того, какие именно числа повторяются. Хранить в каждом узле множество — дорого по памяти и времени.
Префиксные суммы тоже не помогут: у количества различных нет обратной операции, distinct(0..r) - distinct(0..l-1) ничего не значит.
Наивное решение
Для каждого запроса честно пройти отрезок и сложить элементы в множество:
def distinct_naive(a, queries): return [len(set(a[l:r + 1])) for l, r in queries]
Каждый запрос стоит , все вместе — . При это операций, решение не уложится ни в какой лимит.
Шаг к идее: окно, которое умеет двигаться
Заметим, что если мы уже знаем ответ для , ответ для получается за . Заведём массив cnt[x] — сколько раз число x встречается в текущем окне, и счётчик distinct:
- добавить элемент
x:cnt[x] += 1; если стало 1 —distinct += 1; - убрать элемент
x:cnt[x] -= 1; если стало 0 —distinct -= 1.
Это та же механика, что в скользящем окне, только окно может расширяться и сжиматься с обеих сторон. Чтобы перейти от запроса к запросу , нужно операций.
Значит, стоимость всего решения — сумма расстояний между соседними запросами. Если обрабатывать их в исходном порядке, левая и правая границы будут скакать по всему массиву, и мы снова получим . Вопрос в том, в каком порядке обходить запросы, чтобы суммарный путь был маленьким.
Идея Мо: сортировка запросов по блокам
Разобьём индексы массива на блоки длины . Запросы отсортируем так:
- сначала по номеру блока левой границы: ;
- внутри одного блока — по правой границе по возрастанию.
После такой сортировки внутри одного блока правая граница идёт только вперёд, а левая болтается в пределах блока — не дальше чем на позиций. Это и есть весь трюк. Подробнее про саму идею деления на блоки — в статье про корневую декомпозицию.
Почему
Посчитаем движения каждого указателя отдельно.
Правая граница. Внутри одного блока только растёт, поэтому за все запросы блока она пройдёт не больше шагов. При переходе к следующему блоку может откатиться назад — ещё до шагов. Блоков , итого .
Левая граница. Между двумя запросами одного блока сдвигается не больше чем на . Запросов , итого . Переходы между блоками добавляют ещё суммарно.
Складываем:
При получаем . Плюс на сортировку, но это мелочь.
Если сильно отличается от , выгоднее взять : тогда оба слагаемых равны , и сложность становится . На практике для разницы нет, и почти все пишут .
Реализация на Python
from math import isqrt def distinct_mo(a, queries): n = len(a) block = max(1, isqrt(n)) # Сжимаем значения в 0..k-1, чтобы считать в списке, а не в словаре index = {v: i for i, v in enumerate(sorted(set(a)))} b = [index[v] for v in a] cnt = [0] * len(index) order = sorted( range(len(queries)), key=lambda i: (queries[i][0] // block, queries[i][1]), ) ans = [0] * len(queries) cur_l, cur_r = 0, -1 # текущее окно пустое distinct = 0 for qi in order: l, r = queries[qi] while cur_r < r: # расширяем вправо cur_r += 1 cnt[b[cur_r]] += 1 if cnt[b[cur_r]] == 1: distinct += 1 while cur_l > l: # расширяем влево cur_l -= 1 cnt[b[cur_l]] += 1 if cnt[b[cur_l]] == 1: distinct += 1 while cur_r > r: # сжимаем справа cnt[b[cur_r]] -= 1 if cnt[b[cur_r]] == 0: distinct -= 1 cur_r -= 1 while cur_l < l: # сжимаем слева cnt[b[cur_l]] -= 1 if cnt[b[cur_l]] == 0: distinct -= 1 cur_l += 1 ans[qi] = distinct return ans a = [1, 2, 1, 3, 2, 2, 4, 1] queries = [(0, 3), (2, 5), (1, 6), (0, 7), (4, 4)] print(distinct_mo(a, queries)) # [3, 3, 4, 4, 1]
Несколько деталей, которые легко упустить:
- Ответы пишем по исходному индексу
ans[qi], а не по порядку обработки. Сортируем мы индексы запросов, а не сами запросы, — так проще не перепутать. - Окно стартует пустым:
cur_l = 0, cur_r = -1. Тогда первый запрос просто «наращивает» окно с нуля, и отдельный код инициализации не нужен. - Сжатие координат нужно, если значения большие (до ) — массив
cntтакого размера не создать. Словарь тоже работает, но список с целыми индексами заметно быстрее.
Разбор на примере
Возьмём массив и запросы из начала статьи. , .
| Запрос | Блок |
|---|---|
| (0, 3) | 0 |
| (2, 5) | 1 |
| (1, 6) | 0 |
| (0, 7) | 0 |
| (4, 4) | 2 |
После сортировки по (блок, r) порядок обработки такой:
| Шаг | Запрос | Сдвигов указателей | Окно | distinct |
|---|---|---|---|---|
| 1 | (0, 3) | 4 (r: −1 → 3) | 1 2 1 3 | 3 |
| 2 | (1, 6) | 4 (r: 3 → 6, l: 0 → 1) | 2 1 3 2 2 4 | 4 |
| 3 | (0, 7) | 2 (r: 6 → 7, l: 1 → 0) | 1 2 1 3 2 2 4 1 | 4 |
| 4 | (2, 5) | 4 (r: 7 → 5, l: 0 → 2) | 1 3 2 2 | 3 |
| 5 | (4, 4) | 3 (r: 5 → 4, l: 2 → 4) | 2 | 1 |
Всего 17 сдвигов против 23 элементов, которые прошёл бы наивный алгоритм. На восьми элементах выигрыш скромный, но на больших данных разница — несколько порядков. Я замерил на случайных данных с : в исходном порядке указатели делают около шагов, после сортировки Мо — около .
Оптимизация «чёт-нечет»
Посмотрите, что происходит на границе блоков: в конце блока дошёл почти до конца массива, а первый запрос следующего блока начинает с маленького . Указатель откатывается через весь массив впустую.
Лечится одной строкой: в нечётных блоках сортировать по убыванию. Тогда правая граница ходит «змейкой»: туда в одном блоке, обратно — в следующем.
def mo_order(queries, block): def key(i): l, r = queries[i] b = l // block return (b, r if b % 2 == 0 else -r) return sorted(range(len(queries)), key=key)
Асимптотика не меняется, но на тех же случайных запросах число сдвигов упало с до — примерно на треть. Бесплатное ускорение, которое стоит писать всегда.
Есть и более сильный вариант — сортировка вдоль кривой Гильберта. Она даёт ещё немного выигрыша на больших входах, но код заметно сложнее. На собеседовании о ней достаточно знать, что она существует.
Реализация на JavaScript
В Python алгоритм Мо работает медленно: на версия выше у меня считалась около 9 секунд. Это не проблема алгоритма — просто каждый шаг указателя в интерпретаторе стоит дорого. В JS с типизированными массивами тот же вход обрабатывается примерно за полсекунды.
function distinctMo(a, queries) { const n = a.length const block = Math.max(1, Math.floor(Math.sqrt(n))) // Сжатие значений const sorted = [...new Set(a)].sort((x, y) => x - y) const id = new Map(sorted.map((v, i) => [v, i])) const b = Int32Array.from(a, (v) => id.get(v)) const cnt = new Int32Array(sorted.length) const order = queries.map((_, i) => i) order.sort((i, j) => { const bi = Math.floor(queries[i][0] / block) const bj = Math.floor(queries[j][0] / block) if (bi !== bj) return bi - bj // чётные блоки — r по возрастанию, нечётные — по убыванию return bi % 2 === 0 ? queries[i][1] - queries[j][1] : queries[j][1] - queries[i][1] }) const ans = new Array(queries.length) let curL = 0 let curR = -1 let distinct = 0 const add = (i) => { if (cnt[b[i]]++ === 0) distinct++ } const remove = (i) => { if (--cnt[b[i]] === 0) distinct-- } for (const qi of order) { const [l, r] = queries[qi] while (curR < r) add(++curR) while (curL > l) add(--curL) while (curR > r) remove(curR--) while (curL < l) remove(curL++) ans[qi] = distinct } return ans } console.log( distinctMo( [1, 2, 1, 3, 2, 2, 4, 1], [ [0, 3], [2, 5], [1, 6], [0, 7], [4, 4], ] ) ) // [ 3, 3, 4, 4, 1 ]
Здесь логика вынесена в add и remove — так шаблон проще переиспользовать: для новой задачи меняются только эти две функции.
Шаблон: меняем только add и remove
Сила алгоритма Мо в том, что каркас одинаков для любой задачи. Возьмём другую: сколько пар с на отрезке.
Когда в окно приходит элемент x, он образует пару с каждым уже лежащим там x — то есть добавляет cnt[x] пар. При удалении — наоборот.
from math import isqrt def equal_pairs_mo(a, queries): block = max(1, isqrt(len(a))) cnt = {} pairs = 0 def add(i): nonlocal pairs c = cnt.get(a[i], 0) pairs += c # новый элемент образует пару с каждым равным cnt[a[i]] = c + 1 def remove(i): nonlocal pairs c = cnt[a[i]] - 1 cnt[a[i]] = c pairs -= c ans = [0] * len(queries) cur_l, cur_r = 0, -1 for qi in mo_order(queries, block): l, r = queries[qi] while cur_r < r: cur_r += 1 add(cur_r) while cur_l > l: cur_l -= 1 add(cur_l) while cur_r > r: remove(cur_r) cur_r -= 1 while cur_l < l: remove(cur_l) cur_l += 1 ans[qi] = pairs return ans a = [1, 2, 1, 3, 2, 2, 4, 1] queries = [(0, 3), (2, 5), (1, 6), (0, 7), (4, 4)] print(equal_pairs_mo(a, queries)) # [1, 1, 3, 6, 0]
mo_order — функция из раздела про оптимизацию «чёт-нечет». Таким же образом решаются:
- сумма на отрезке («сила подмассива», классика Codeforces);
- количество чисел, встречающихся ровно раз;
- число подотрезков с XOR, равным (через префиксные XOR — запрос по массиву префиксов);
- наиболее частый элемент, если поддерживать ещё и
freq_of_cnt— сколько чисел встречаются ровно раз.
Условие одно: и add, и remove должны работать за (или хотя бы быстро). Если удалить элемент дёшево нельзя — например, при поиске максимума, — нужна модификация «Мо с откатами», где окно только растёт, а лишнее отменяется по журналу изменений.
Когда Мо не подходит
- Запросы приходят онлайн. Если следующий запрос зависит от ответа на предыдущий (на олимпиадах это делают, например, через XOR с прошлым ответом), переставлять запросы нельзя.
- Массив меняется. Обычный Мо этого не умеет. Есть «Мо с обновлениями» — сортировка по трём координатам , где — время. Сложность , и это уже совсем олимпиадная техника.
- Ответ ассоциативен. Сумма, минимум, НОД на отрезке решаются деревом отрезков или деревом Фенвика за на запрос и ещё поддерживают обновления. Мо здесь проигрывает.
Кстати, именно для числа различных элементов есть и оффлайн-решение за : сортируем запросы по , идём слева направо и в дереве Фенвика держим единицу только в последнем вхождении каждого значения. Ответ на — сумма на . Оно быстрее, но придумать его сложнее, а Мо обобщается на десятки задач без изменения каркаса.
Типичные ошибки
Сначала сжимают, потом расширяют. Порядок четырёх циклов важен: сначала расширяем окно, потом сужаем. Если начать с удаления, окно на мгновение может стать «отрицательным» (), счётчики уйдут в минус, а проверки cnt == 0 и cnt == 1 начнут срабатывать не тогда. Ответ сломается тихо, без исключений.
Ответы записывают по порядку обработки. После сортировки -й обработанный запрос — не -й во входе. Сортируйте индексы и пишите в ans[qi].
Размер блока 0. isqrt(1) = 1, но если считать блок как int(n ** 0.5) для пустого массива или делить на n // q, легко получить ноль и деление на ноль. max(1, ...) спасает.
Сортировка по , а не по блоку . Если сортировать просто по паре , правая граница будет прыгать на каждом запросе, и сложность вернётся к . Вся магия — в округлении до блока.
Словарь вместо массива в горячем цикле. Асимптотика та же, но константа в разы больше. При больших значениях делайте сжатие координат один раз в начале.
Границы включительно или нет. В статье отрезки с включёнными концами и нумерацией с нуля. Если во входе нумерация с единицы, вычтите 1 сразу при чтении — не пытайтесь подстраивать условия циклов.
Где встречается на собеседованиях
Честно: на обычном алгоритмическом собеседовании алгоритм Мо почти не спрашивают — для 45 минут он тяжеловат, и задачи LeetCode обычно решаются без него. Он встречается на олимпиадах, в контестах Codeforces и иногда на секциях с усложнёнными задачами.
Но саму механику — окно с cnt и счётчиком, который обновляется при добавлении и удалении, — спрашивают постоянно. Её стоит довести до автоматизма на задачах вроде «самая длинная подстрока без повторов» или «есть ли дубликат на расстоянии не больше »: это ровно функции add и remove из этой статьи, только окно движется монотонно.
Если интервьюер даёт задачу «много запросов на отрезках, массив не меняется» и ответ не складывается из половинок, — это сигнал вспомнить про Мо. Даже если писать его не придётся, фраза «можно обработать запросы оффлайн, отсортировав по блокам левой границы, это » показывает, что вы знаете инструменты шире стандартного набора.
Итог
- Алгоритм Мо отвечает на оффлайн-запросы на отрезках, переставляя их так, чтобы окно двигалось мало.
- Сортировка: по блоку , внутри — по ; в нечётных блоках по убыванию.
- Сложность , от задачи зависят только
addиremove. - Не работает с онлайн-запросами и обновлениями без модификаций; для ассоциативных операций лучше дерево отрезков или Фенвика.