Решение RMQ с помощью разреженной таблицы

Разреженная таблица (англ. sparse table) позволяет решать задачу online static RMQ за $O(1)$ на запрос, с предподсчётом за $O(N \log N)$ и использованием $O(N \log N)$ памяти.

Постановка задачи RMQ

Дан массив $A[1..N]$ целых чисел. Поступают запросы вида $(l, r)$: найти минимум в подмассиве $A[l], A[l + 1], \dots, A[r]$.

Разреженная таблица

Разреженная таблица — двумерная структура данных $ST[i, j]$, для которой выполнено следующее: $ST[i][j]=\min\left(A[i], A[i+1], ..., A[i+2^{j}-1]\right),\quad j \in [0 .. \log N]$. Иначе говоря, в этой таблице хранятся минимумы на всех отрезках, длины которых равны степеням двойки. Объём, занимаемый таблицей, равен $O(N \log N)$, и заполненными являются только те элементы, для которых $i+2^j \le N$.

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

$ST[i][j] = \left\{ \begin{array}{rcl} \min\left(ST[i][j-1], ST[i+2^{j-1}][j-1]\right), j \gt 0 \\ A[i], j = 0 \\ \end{array} \right.$ .

Идемпотентность

Такая простота достигается за счет идемпотентности операции минимум: $\min(a, a)=a$. Это один из ключевых моментов этого метода, так как она позволяет нам корректно считать минимум в области пересечения отрезков. <wikitex> Пусть $\circ$ — произвольная бинарная операция, которая удовлетворяет свойствам:

• ассоциативности: $a \circ (b \circ c) = (a \circ b) \circ c$;
• коммутативности: $a \circ b = b \circ a$;
• идемпотентности: $a \circ a = a$.

Утверждение:

$a_l \circ a_{l+1} \circ \dots \circ a_r = (a_l \circ a_{l+1} \circ \dots \circ a_k) \circ (a_{r - k} \circ a_{r - k + 1} \circ \dots \circ a_r)$, где $l \leqslant k \leqslant r; \frac{l}{2} \leqslant k$.

$\triangleright$

Отрезок $(a_{r-k}, a_k)$ содержится в обои операндах правой части. Значит, каждый элемент из него входит два раза. По коммутативности мы можем расположить повторяющиеся элементы друг с другом. По ассоциотивности мы можем расставлять скобки как угодно, в том числе, обособляя эти самые повторы. А за счет идемпотентности мы от них избавляемся. В итоге, получаем выражение в левой части равенства.

$\triangleleft$

</wikitex>

Применение к задаче RMQ

Предпосчитаем длину отрезка $k$. Это можно сделать за $O(N\log N)$ введением функции $fl[l] = k$, для которой верно $fl[1] = 0, fl[x] = fl[\lfloor \frac{x}{2}\rfloor] + 1$.

Пусть теперь дан запрос $(l, r)$. Заметим, что $\min(A[l], A[l+1], ..., A[r]) = \min\left(ST[l][k], ST[r-2^k+1][j]\right)$, где $k = \max \{j| 2^j \le r - l + 1\}$, т.е. логарифм длины запрашиваемого отрезка, округленный вниз. Но эту величину мы уже предпосчитали, поэтому запрос выполняется за $O (1)$.

Стоит отметить, что этот метод работает не только с операцией минимум, но и с любой идемпотентной, ассоциативной и коммутативной операцией, так как отрезки $(l, 2^k)$ и $(r - 2^k, r)$, на которых мы считаем ответ, есть те самые из доказанного утверждения. Таким образом мы получаем целый класс задач, решаемых разреженной таблицей.

См. также

• Сведение задачи LCA к задаче RMQ
• Алгоритм Фарака-Колтона и Бендера
• Сведение задачи RMQ к задаче LCA

Источники

• Bender, M.A., Farach-Colton, M. et al. — Lowest common ancestors in trees and directed acyclic graphs. — J. Algorithms 57(2) (2005) — с. 75–94.