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

2012-04-22T11:25:35Z

178.178.14.56: small fix

'''Разреженная таблица''' (англ. ''sparse table'') позволяет решать задачу online static RMQ за <tex>O(1)</tex> на запрос, с предподсчётом за <tex>O(N \log N)</tex> и использованием <tex>O(N \log N)</tex> памяти.
== Постановка задачи RMQ ==
Дан массив <tex>A[1..N]</tex> действительных чисел. Поступают запросы вида <tex>(l, r)</tex>: найти минимум в подмассиве <tex>A[l], A[l + 1], \dots, A[r] </tex>.

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

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

<tex> ST[i][j] =
\left\{
\begin{array}{rcl}
\min\left(ST[i][j-1], ST[i+2^{j-1}][j-1]\right), j > 0 \\
A[i], j = 0 \\
\end{array}
\right.
</tex> .
=== Идемпотентность ===
Такая простота достигается за счет идемпотентности операции минимум: <tex>\min(a, a)=a</tex>. Это один из ключевых моментов этого метода, так как она позволяет нам корректно считать минимум в области пересечения отрезков.
<wikitex>
Пусть $\circ$ — произвольная бинарная операция, которая удовлетворяет свойствам:
* ассоциативности: $a \circ (b \circ c) = (a \circ b) \circ c $;
* коммутативности: $a \circ b = b \circ a$;
* идемпотентности: $a \circ a = a $.

{{Утверждение
|statement=
$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$.
|proof=
Покажем, что $a \circ b \circ c \circ d = (a \circ b \circ c) \circ (b \circ c \circ d)$. Действительно, $a \circ b \circ c \circ b \circ c \circ d = a \circ b \circ b \circ c \circ c \circ d = a \circ b \circ c \circ d $. Будем применять это к выражению в правой части равенства до тех пор, пока не получим выражение в левой части. Поле каждого шага количество одинаковых элементов сократится на два. А так как их конечное четное (по $2k - r$ в каждой скобке) число, то и количество шагов будет конечным.
}}
Таким образом мы получаем целый класс задач, которые могут решаться разреженной таблицей.
</wikitex>

== Применение к задаче RMQ ==
[[Файл:SparseTableRMQ.png|right|Решение задачи RMQ на разреженной таблице]]
<div>Дан запрос <tex>(l, r)</tex>. По нему найдем <tex>k = \max \{j| 2^j \le r - l + 1\}</tex>, т.е. логарифм длины запрашиваемого отрезка. Заметим, что <tex>k</tex> зависит лишь от длины отрезка. Предпосчитать эту величину за <tex>O(N\log N)</tex> можно введением функции <tex>fl[l] = k</tex>, для которой верно <tex>fl[1] = 0, fl[x] = fl[\lfloor \frac{x}{2}\rfloor] + 1</tex>.
Далее заметим, что <tex>\min(A[l], A[l+1], ..., A[r]) = \min\left(ST[l][k], ST[r-2^k+1][j]\right)</tex>. Таким образом мы можем находить <tex>k</tex> за <tex>O(1)</tex>.</div>
<div style="clear:both"></div>

== См. также ==
* [[Сведение задачи LCA к задаче RMQ | Сведение задачи LCA к задаче RMQ]]
* [[Алгоритм Фарака-Колтона и Бендера | Алгоритм Фарака-Колтона и Бендера]]
* [[Сведение задачи RMQ к задаче LCA | Сведение задачи 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.

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Задача о наименьшем общем предке]]

Викиконспекты - Вклад участника [ru]

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