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

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

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

Дан массив [math]A[1..N][/math] целых чисел. Поступают запросы вида [math](l, r)[/math], для каждого из которых требуется найти минимум среди элементов [math]A[l], A[l + 1], \dots, A[r] [/math].

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

Разреженная таблица — двумерная структура данных [math]ST[i][j][/math], для которой выполнено следующее:

[math]ST[i][j]=\min\left(A[i], A[i+1], ..., A[i+2^{j}-1]\right),\quad j \in [0 .. \log N][/math].

Иначе говоря, в этой таблице хранятся минимумы на всех отрезках, длины которых равны степеням двойки. Объём памяти, занимаемый таблицей, равен [math]O(N \log N)[/math], и заполненными являются только те элементы, для которых [math]i+2^j \le N [/math].

Простой метод построения таблицы заключён в следующем реккурентном соотношении: <wikitex>$$ST[i][j]= \begin{cases} \min\left(ST[i][j-1], ST[i+2^{j-1}][j-1]\right),&\text{если $j > 0$;}\\ A[i], &\text{если $j = 0$;} \end{cases} $$ </wikitex>

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

Такая простота достигается за счет идемпотентности операции минимум: [math]\min(a, a)=a[/math]. Это один из ключевых моментов этого метода, так как она позволяет нам корректно считать минимум в области пересечения отрезков. <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$.

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

</wikitex>

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

Предпосчитаем для длины отрезка [math]l[/math] величину [math]j =\lfloor \log_2l \rfloor[/math]. Для этого введем функцию [math]fl[l] = j[/math], для которой верно [math]fl[1] = 0, fl[x] = fl[\lfloor \frac{x}{2}\rfloor] + 1[/math]. Вычисление [math]fl[l][/math] происходит за [math]O(\log (l))[/math]. А, так как длина может принимать [math]N[/math] различных значений, то суммарное время предпосчета составляет [math]O(N\log N)[/math].

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

Из выше доказанной теоремы следует, что этот метод работает не только с операцией минимум, но и с любой идемпотентной, ассоциативной и коммутативной операцией. Таким образом мы получаем целый класс задач, решаемых разреженной таблицей.

См. также

• Сведение задачи 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.