74
правки
Изменения
Тикет 5-4
'''Разреженная таблица''' (англ. ''sparse table'') позволяет решать задачу online static RMQ (получение минимума или максимума на отрезке, когда элементы массива не могут изменяться, а запросы поступают последовательно) за <tex>O(1)</tex> на запрос, с предподсчётом за <tex>O(N \log N)</tex> и использованием <tex>O(N \log N)</tex> памяти. {{Задача|definition == Постановка задачи RMQ ==Дан массив <tex>A[1..\ldots N]</tex> целых чисел. Поступают запросы вида <tex>(l, r)</tex>, для каждого из которых требуется найти минимум среди элементов <tex>A[l], A[l + 1], \dotsldots, A[r] </tex>.}}
== Разреженная таблица ==
Разреженная таблица — двумерная структура данных <tex>ST[i][j]</tex>, для которой выполнено следующее:
<tex>ST[i][j]=\min\left(A[i], A[i+1], ...\ldots, A[i+2^{j}-1]\right),\quad j \in [0 .. \ldots \log N]</tex>.
Иначе говоря, в этой таблице хранятся минимумы на всех отрезках, длины которых равны степеням двойки. Объём памяти, занимаемый таблицей, равен <tex>O(N \log N)</tex>, и заполненными являются только те элементы, для которых <tex>i+2^j \le leqslant N </tex>.
Простой метод построения таблицы заключён в следующем реккурентном соотношении:
$$
</wikitex>
Такая простота достигается за счет идемпотентности операции минимум: <tex>\min(a, a)=a</tex>. Это один из ключевых моментов этого метода, так как она позволяет нам корректно считать минимум в области пересечения отрезков.
<wikitex>
{{Утверждение
|statement=
$a_l \circ a_{l+1} \circ \dots ldots \circ a_r = (a_l \circ a_{l+1} \circ \dots ldots \circ a_k) \circ (a_{r - k} \circ a_{r - k + 1} \circ \dots ldots \circ a_r)$, где $l \leqslant k \leqslant r$.
|proof=
Отрезок $(a_{r-k}, a_k)$ содержится в обои операндах правой части. Значит, каждый элемент из него входит два раза. По коммутативности мы можем располагать элементы в любом порядке, по ассоциативности мы можем выполнять операции в произвольном порядке, поэтому повторяющие в правой части элементы мы можем расположить рядом друг с другом и затем по идемпотентности один из них убрать. Переставляя оставшиеся элементы в правой затем легко получаем выражение в левой части.
== Применение к задаче RMQ ==
<div> Предпосчитаем для длины отрезка <tex>l</tex> величину <tex>\lfloor \log_2l \rfloor</tex>. Для этого введем функцию <tex>fl</tex>:
'''fl''' ('''int''' len):
'''if''' len <tex>=</tex> 1:
'''return''' 0
'''else''':
'''return''' fl(<tex>\lfloor \cfrac{len}{2}\rfloor</tex>) + 1
Вычисление <tex>fl[l]</tex> происходит за <tex>O(\log (l))</tex>. А так как длина может принимать <tex>N</tex> различных значений, то суммарное время предпосчета составляет <tex>O(N\log N)</tex>.
Пусть теперь дан запрос <tex>(l, r)</tex>. Заметим, что <tex>\min(A[l], A[l+1], \ldots, A[r]) = \min\left(ST[l][j], ST[r-2^j+1][j]\right)</tex>, где <tex>j = \max \{k \mid 2^k \leqslant r - l + 1\}</tex>, то есть логарифм длины запрашиваемого отрезка, округленный вниз. Но эту величину мы уже предпосчитали, поэтому запрос выполняется за <tex>O (1)</tex>.
[[Файл:SparseTableRMQ.png|right|Решение задачи 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.
