Алгоритм Мо: запросы на отрезках оффлайн за O((n+q)√n)

Алгоритм Мо простыми словами: как отсортировать запросы по блокам, двигать два указателя и считать число различных элементов на отрезке за O((n+q)√n). Код на Python и JS.

8 мин чтенияалгоритмы · запросы на отрезках · корневая декомпозиция · python

Коротко

ЧтоЗначение
ЗадачаОтветить на qq запросов вида «посчитай что-то на отрезке [l,r][l, r]»
УсловиеВсе запросы известны заранее (оффлайн), массив не меняется
Главная идеяПереставить запросы так, чтобы окно [l,r][l, r] двигалось мало
СортировкаПо блоку ⌊l/n⌋\lfloor l / \sqrt{n} \rfloor, внутри блока — по rr
СложностьO((n+q)n)O((n + q)\sqrt{n}) вызовов add/remove + O(qlog⁡q)O(q \log q) на сортировку
Что нужно уметьДобавить элемент в окно и убрать его за O(1)O(1)

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

Задача: число различных элементов на отрезке

Дан массив a длины nn и qq запросов (l,r)(l, r). Для каждого нужно сказать, сколько различных чисел лежит в 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]

Каждый запрос стоит O(n)O(n), все вместе — O(nq)O(nq). При n=q=2⋅105n = q = 2 \cdot 10^5 это 4⋅10104 \cdot 10^{10} операций, решение не уложится ни в какой лимит.

Шаг к идее: окно, которое умеет двигаться

Заметим, что если мы уже знаем ответ для [l,r][l, r], ответ для [l,r+1][l, r+1] получается за O(1)O(1). Заведём массив cnt[x] — сколько раз число x встречается в текущем окне, и счётчик distinct:

  • добавить элемент x: cnt[x] += 1; если стало 1 — distinct += 1;
  • убрать элемент x: cnt[x] -= 1; если стало 0 — distinct -= 1.

Это та же механика, что в скользящем окне, только окно может расширяться и сжиматься с обеих сторон. Чтобы перейти от запроса (l1,r1)(l_1, r_1) к запросу (l2,r2)(l_2, r_2), нужно ∣l1−l2∣+∣r1−r2∣|l_1 - l_2| + |r_1 - r_2| операций.

Значит, стоимость всего решения — сумма расстояний между соседними запросами. Если обрабатывать их в исходном порядке, левая и правая границы будут скакать по всему массиву, и мы снова получим O(nq)O(nq). Вопрос в том, в каком порядке обходить запросы, чтобы суммарный путь был маленьким.

Идея Мо: сортировка запросов по блокам

Разобьём индексы массива на блоки длины B≈nB \approx \sqrt{n}. Запросы отсортируем так:

  1. сначала по номеру блока левой границы: ⌊l/B⌋\lfloor l / B \rfloor;
  2. внутри одного блока — по правой границе rr по возрастанию.

После такой сортировки внутри одного блока правая граница идёт только вперёд, а левая болтается в пределах блока — не дальше чем на BB позиций. Это и есть весь трюк. Подробнее про саму идею деления на блоки — в статье про корневую декомпозицию.

Почему O((n+q)n)O((n + q)\sqrt{n})

Посчитаем движения каждого указателя отдельно.

Правая граница. Внутри одного блока rr только растёт, поэтому за все запросы блока она пройдёт не больше nn шагов. При переходе к следующему блоку rr может откатиться назад — ещё до nn шагов. Блоков n/Bn / B, итого O(n⋅n/B)O(n \cdot n / B).

Левая граница. Между двумя запросами одного блока ll сдвигается не больше чем на BB. Запросов qq, итого O(q⋅B)O(q \cdot B). Переходы между блоками добавляют ещё O(n)O(n) суммарно.

Складываем:

O(n2B+qB+n)O\left(\frac{n^2}{B} + qB + n\right)

При B=nB = \sqrt{n} получаем O(nn+qn)=O((n+q)n)O(n\sqrt{n} + q\sqrt{n}) = O((n + q)\sqrt{n}). Плюс O(qlog⁡q)O(q \log q) на сортировку, но это мелочь.

Если qq сильно отличается от nn, выгоднее взять B=n/qB = n / \sqrt{q}: тогда оба слагаемых равны nqn\sqrt{q}, и сложность становится O(nq)O(n\sqrt{q}). На практике для n≈qn \approx q разницы нет, и почти все пишут n\sqrt{n}.

Реализация на 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. Тогда первый запрос просто «наращивает» окно с нуля, и отдельный код инициализации не нужен.
  • Сжатие координат нужно, если значения большие (до 10910^9) — массив cnt такого размера не создать. Словарь тоже работает, но список с целыми индексами заметно быстрее.

Разбор на примере

Возьмём массив и запросы из начала статьи. n=8n = 8, B=⌊8⌋=2B = \lfloor\sqrt{8}\rfloor = 2.

ЗапросБлок l/Bl / B
(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 33
2(1, 6)4 (r: 3 → 6, l: 0 → 1)2 1 3 2 2 44
3(0, 7)2 (r: 6 → 7, l: 1 → 0)1 2 1 3 2 2 4 14
4(2, 5)4 (r: 7 → 5, l: 0 → 2)1 3 2 23
5(4, 4)3 (r: 5 → 4, l: 2 → 4)21

Всего 17 сдвигов против 23 элементов, которые прошёл бы наивный алгоритм. На восьми элементах выигрыш скромный, но на больших данных разница — несколько порядков. Я замерил на случайных данных с n=q=2⋅105n = q = 2 \cdot 10^5: в исходном порядке указатели делают около 2.3⋅10102.3 \cdot 10^{10} шагов, после сортировки Мо — около 1.2⋅1081.2 \cdot 10^8.

Оптимизация «чёт-нечет»

Посмотрите, что происходит на границе блоков: в конце блока rr дошёл почти до конца массива, а первый запрос следующего блока начинает с маленького rr. Указатель откатывается через весь массив впустую.

Лечится одной строкой: в нечётных блоках сортировать rr по убыванию. Тогда правая граница ходит «змейкой»: туда в одном блоке, обратно — в следующем.

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)

Асимптотика не меняется, но на тех же 2⋅1052 \cdot 10^5 случайных запросах число сдвигов упало с 1.19⋅1081.19 \cdot 10^8 до 7.5⋅1077.5 \cdot 10^7 — примерно на треть. Бесплатное ускорение, которое стоит писать всегда.

Есть и более сильный вариант — сортировка вдоль кривой Гильберта. Она даёт ещё немного выигрыша на больших входах, но код заметно сложнее. На собеседовании о ней достаточно знать, что она существует.

Реализация на JavaScript

В Python алгоритм Мо работает медленно: на n=q=2⋅105n = q = 2 \cdot 10^5 версия выше у меня считалась около 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

Сила алгоритма Мо в том, что каркас одинаков для любой задачи. Возьмём другую: сколько пар i<ji < j с ai=aja_i = a_j на отрезке.

Когда в окно приходит элемент 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 — функция из раздела про оптимизацию «чёт-нечет». Таким же образом решаются:

  • сумма ∑cnt[x]2⋅x\sum cnt[x]^2 \cdot x на отрезке («сила подмассива», классика Codeforces);
  • количество чисел, встречающихся ровно kk раз;
  • число подотрезков с XOR, равным kk (через префиксные XOR — запрос по массиву префиксов);
  • наиболее частый элемент, если поддерживать ещё и freq_of_cnt — сколько чисел встречаются ровно cc раз.

Условие одно: и add, и remove должны работать за O(1)O(1) (или хотя бы быстро). Если удалить элемент дёшево нельзя — например, при поиске максимума, — нужна модификация «Мо с откатами», где окно только растёт, а лишнее отменяется по журналу изменений.

Когда Мо не подходит

  • Запросы приходят онлайн. Если следующий запрос зависит от ответа на предыдущий (на олимпиадах это делают, например, через XOR с прошлым ответом), переставлять запросы нельзя.
  • Массив меняется. Обычный Мо этого не умеет. Есть «Мо с обновлениями» — сортировка по трём координатам (l,r,t)(l, r, t), где tt — время. Сложность O(n5/3)O(n^{5/3}), и это уже совсем олимпиадная техника.
  • Ответ ассоциативен. Сумма, минимум, НОД на отрезке решаются деревом отрезков или деревом Фенвика за O(log⁡n)O(\log n) на запрос и ещё поддерживают обновления. Мо здесь проигрывает.

Кстати, именно для числа различных элементов есть и оффлайн-решение за O((n+q)log⁡n)O((n + q)\log n): сортируем запросы по rr, идём слева направо и в дереве Фенвика держим единицу только в последнем вхождении каждого значения. Ответ на (l,r)(l, r) — сумма на [l,r][l, r]. Оно быстрее, но придумать его сложнее, а Мо обобщается на десятки задач без изменения каркаса.

Типичные ошибки

Сначала сжимают, потом расширяют. Порядок четырёх циклов важен: сначала расширяем окно, потом сужаем. Если начать с удаления, окно на мгновение может стать «отрицательным» (l>r+1l > r + 1), счётчики уйдут в минус, а проверки cnt == 0 и cnt == 1 начнут срабатывать не тогда. Ответ сломается тихо, без исключений.

Ответы записывают по порядку обработки. После сортировки ii-й обработанный запрос — не ii-й во входе. Сортируйте индексы и пишите в ans[qi].

Размер блока 0. isqrt(1) = 1, но если считать блок как int(n ** 0.5) для пустого массива или делить на n // q, легко получить ноль и деление на ноль. max(1, ...) спасает.

Сортировка по ll, а не по блоку ll. Если сортировать просто по паре (l,r)(l, r), правая граница будет прыгать на каждом запросе, и сложность вернётся к O(nq)O(nq). Вся магия — в округлении ll до блока.

Словарь вместо массива в горячем цикле. Асимптотика та же, но константа в разы больше. При больших значениях делайте сжатие координат один раз в начале.

Границы включительно или нет. В статье отрезки [l,r][l, r] с включёнными концами и нумерацией с нуля. Если во входе нумерация с единицы, вычтите 1 сразу при чтении — не пытайтесь подстраивать условия циклов.

Где встречается на собеседованиях

Честно: на обычном алгоритмическом собеседовании алгоритм Мо почти не спрашивают — для 45 минут он тяжеловат, и задачи LeetCode обычно решаются без него. Он встречается на олимпиадах, в контестах Codeforces и иногда на секциях с усложнёнными задачами.

Но саму механику — окно с cnt и счётчиком, который обновляется при добавлении и удалении, — спрашивают постоянно. Её стоит довести до автоматизма на задачах вроде «самая длинная подстрока без повторов» или «есть ли дубликат на расстоянии не больше kk»: это ровно функции add и remove из этой статьи, только окно движется монотонно.

Если интервьюер даёт задачу «много запросов на отрезках, массив не меняется» и ответ не складывается из половинок, — это сигнал вспомнить про Мо. Даже если писать его не придётся, фраза «можно обработать запросы оффлайн, отсортировав по блокам левой границы, это O((n+q)n)O((n + q)\sqrt{n})» показывает, что вы знаете инструменты шире стандартного набора.

Итог

  • Алгоритм Мо отвечает на оффлайн-запросы на отрезках, переставляя их так, чтобы окно двигалось мало.
  • Сортировка: по блоку ⌊l/n⌋\lfloor l / \sqrt{n} \rfloor, внутри — по rr; в нечётных блоках rr по убыванию.
  • Сложность O((n+q)n)O((n + q)\sqrt{n}), от задачи зависят только add и remove.
  • Не работает с онлайн-запросами и обновлениями без модификаций; для ассоциативных операций лучше дерево отрезков или Фенвика.

Потренироваться в спокойной обстановке

Все задачи