Изменения

'''Разреженная таблица''' (англ. ''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> 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> .=== Идемпотентность ===

* ассоциативности: $a \circ (b \circ c) = (a \circ b) \circ c $;,* коммутативности: $a \circ b = b \circ a$;,

$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$.

Отрезок $(a_{r-k}, a_ka_{l + k})$ содержится в обои обоих операндах правой части. Значит, каждый элемент из него входит два раза. По коммутативности мы можем расположить повторяющиеся располагать элементы друг с другом. По ассоциотивности в любом порядке, по ассоциативности мы можем расставлять скобки как угодновыполнять операции в произвольном порядке, поэтому повторяющие в том числе, обособляя эти самые повторы. А за счет правой части элементы мы можем расположить рядом друг с другом и затем по идемпотентности мы от один из них избавляемсяубрать. В итоге, Переставляя оставшиеся элементы в правой затем легко получаем выражение в левой части равенства.

Пусть теперь дан запрос <div> Предпосчитаем для длины отрезка <tex>(l, r)</tex> величину <tex>\lfloor \log_2l \rfloor</tex>. Заметим, что Для этого введем функцию <tex>\minfl</tex> (A[l], A[l+1]от ''floor'', т.к.., A[r]логарифм округляется вниз):  '''int''' '''fl'''('''int''' len) : '''if''' len <tex>= </tex> 1 '''return''' 0 '''else''' '''return''' fl(<tex>\minlfloor \left(ST[l][k], ST[r-cfrac{len}{2^k}\rfloor</tex>) +1] Вычисление <tex>fl[jl]\right)</tex>, где происходит за <tex>k = O(\max \{j| 2^j \le r - log (l + 1\}))</tex>, т.е. логарифм длины запрашиваемого отрезка, округленный вниз. Но эту величину мы уже предпосчиталиА так как длина может принимать <tex>N</tex> различных значений, поэтому запрос выполняется за то суммарное время предпосчета составляет <tex>O (1N\log N)</tex>.

== Источники информации==