Решение RMQ с помощью разреженной таблицы — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Разреженная таблица)
(Применение к задаче RMQ)
Строка 9: Строка 9:
 
== Применение к задаче RMQ ==
 
== Применение к задаче RMQ ==
 
[[Файл:SparseTableRMQ.png|right|Решение задачи RMQ на разреженной таблице]]
 
[[Файл:SparseTableRMQ.png|right|Решение задачи RMQ на разреженной таблице]]
<div>Дан запрос <tex>(l, r)</tex>. По нему найдём <tex>\max j: 2^j \le r - l + 1</tex>, т.е. логарифм длины запрашиваемого отрезка.
+
<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, j], ST[r-2^j+1,j]\right)</tex>. Таким образом, если находить <tex>j</tex> за <tex>O(1)</tex> (например, предподсчётом за <tex>O(N \log N)</tex> для всех возможных длин отрезков), можно отвечать на запрос за константное время.</div>
+
Заметим, что <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>
 
<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.
 
* ''Bender, M.A., Farach-Colton, M. et al.'' — '''Lowest common ancestors in trees and directed acyclic graphs'''. — J. Algorithms 57(2) (2005) —  с. 75–94.

Версия 00:25, 26 марта 2012

Разреженная таблица (англ. 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[/math], начиная с позиции [math]l[/math] и заканчивая позицией [math]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].

Простой метод построения таблицы заключён в следующем реккурентном соотношении: [math]ST[i,j]=\min\left(ST[i,j-1], ST[i+2^{j-1}, j-1]\right)[/math], что достигается за счет идемпотентности операции минимум: [math]\min(a, a)=a[/math]. Это один из ключевых моментов этого метода.

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

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

Источники

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