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

2012-03-31T16:58:51Z

88.135.63.26:

'''Разреженная таблица''' (англ. ''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</tex>, начиная с позиции <tex>l</tex> и заканчивая позицией <tex>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}{lcl}
\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>. Это один из ключевых моментов этого метода, так как идемпотентность позволяет нам корректно считать минимум в области пересечения отрезков.

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

== Источники ==
* ''Bender, M.A., Farach-Colton, M. et al.'' — '''Lowest common ancestors in trees and directed acyclic graphs'''. — J. Algorithms 57(2) (2005) — с. 75–94.

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

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

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

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