Изменения

'''Разреженная таблица''' (англ. ''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</tex>[l], начиная с позиции <tex>A[l</tex> и заканчивая позицией <tex>+ 1], \ldots, A[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]=\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 \leqslant N </tex>. Простой метод построения таблицы заключён в следующем реккурентном рекуррентном соотношении: <tex>$$ST[i,][j]=\begin{cases}\min\left(ST[i,][j-1], ST[i+2^{j-1}, ][j-1]\right)</tex,&\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 \ldots \circ a_r = (a_l \circ a_{l+1} \circ \ldots \circ a_{l + k}) \circ (a_{r - k} \circ a_{r - k + 1} \circ \ldots \circ a_r)$, где $\frac{r - l}{2} \leqslant k \leqslant r - l$.|proof=Отрезок $(a_{r-k}, a_{l + k})$ содержится в обоих операндах правой части. Значит, каждый элемент из него входит два раза. По коммутативности мы можем располагать элементы в любом порядке, по ассоциативности мы можем выполнять операции в произвольном порядке, поэтому повторяющие в правой части элементы мы можем расположить рядом друг с другом и затем по идемпотентности один из них убрать. Переставляя оставшиеся элементы в правой затем легко получаем выражение в левой части.}}

<div>Дан запрос <tex>(l, r)</tex>. По нему найдём <tex>\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>

 == См. также ==* [[Сведение задачи LCA к задаче RMQ | Сведение задачи LCA к задаче RMQ]]* [[Алгоритм Фарака-Колтона и Бендера | Алгоритм Фарака-Колтона и Бендера]]* [[Сведение задачи RMQ к задаче LCA | Сведение задачи RMQ к задаче LCA]]* [[ Heavy-light декомпозиция | Heavy-light декомпозиция]] == Источники информации==