24
правки
Изменения
м
<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> .=== Идемпотентность ===
<wikitex>
</wikitex>
<div> Предпосчитаем длину отрезка <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>(l, r)</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 = \max \{j| 2^j \le r - l + 1\}</tex>, т.е. логарифм длины запрашиваемого отрезка, округленный вниз. Но эту величину мы уже предпосчитали, поэтому запрос выполняется за <tex>O (1)</tex>. Стоит отметитьИз выше доказанной теоремы следует, что этот метод работает не только с операцией минимум, но и с любой идемпотентной, ассоциативной и коммутативной операцией, так как отрезки <tex>(l, 2^k)</tex> и <tex>(r - 2^k, r)</tex>, на которых мы считаем ответ, есть те самые из доказанного утверждения. Таким образом мы получаем целый класс задач, решаемых разреженной таблицей.
Правка орфографии
'''Разреженная таблица''' (англ. ''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>.
Простой метод построения таблицы заключён в следующем реккурентном рекуррентном соотношении: $$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}$$
Такая простота достигается за счет идемпотентности операции минимум: <tex>\min(a, a)=a</tex>. Это один из ключевых моментов этого метода, так как она позволяет нам корректно считать минимум в области пересечения отрезков.
Пусть $\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 ldots \circ a_r = (a_l \circ a_{l+1} \circ \dots ldots \circ a_ka_{l + k}) \circ (a_{r - k} \circ a_{r - k + 1} \circ \dots ldots \circ a_r)$, где $l \leqslant k \leqslant r; \frac{r - l}{2} \leqslant k\leqslant r - l$.
|proof=
Отрезок $(a_{r-k}, a_ka_{l + k})$ содержится в обои обоих операндах правой части. Значит, каждый элемент из него входит два раза. По коммутативности мы можем расположить повторяющиеся располагать элементы друг с другом. По ассоциотивности в любом порядке, по ассоциативности мы можем расставлять скобки как угодновыполнять операции в произвольном порядке, поэтому повторяющие в том числе, обособляя эти самые повторы. А за счет правой части элементы мы можем расположить рядом друг с другом и затем по идемпотентности мы от один из них избавляемсяубрать. В итоге, Переставляя оставшиеся элементы в правой затем легко получаем выражение в левой части равенства.
}}
== Применение к задаче RMQ ==
<div> Предпосчитаем для длины отрезка <tex>l</tex> величину <tex>\lfloor \log_2l \rfloor</tex>. Для этого введем функцию <tex>fl</tex> (от ''floor'', т.к. логарифм округляется вниз):
'''int''' '''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 на разреженной таблице]]
<div style="clear:both"></div>
* [[Алгоритм Фарака-Колтона и Бендера | Алгоритм Фарака-Колтона и Бендера]]
* [[Сведение задачи RMQ к задаче LCA | Сведение задачи RMQ к задаче LCA]]
* [[ Heavy-light декомпозиция | Heavy-light декомпозиция]]
== Источники информации==
* ''Bender, M.A., Farach-Colton, M. et al.'' — '''Lowest common ancestors in trees and directed acyclic graphs'''. — J. Algorithms 57(2) (2005) — с. 75–94.
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Задача о наименьшем общем предке]]