Изменения
→Разреженная таблица
== Разреженная таблица ==
Разреженная таблица — двумерная структура данных <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>.
Простой метод построения таблицы заключён в следующем реккурентном соотношении:
\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> .
=== Идемпотентность ===
Такая простота достигается за счет идемпотентности операции минимум: <tex>\min(a, a)=a</tex>. Это один из ключевых моментов этого метода, так как она позволяет нам корректно считать минимум в области пересечения отрезков.
{{Утверждение
|statement=
$a_l \circ a_{l+1} \circ \dots \circ a_r = (a_l \circ a_{l+1} \circ \dots \circ a_k) \circ (a_{r - k} \circ a_{r - k + 1} \circ \dots \circ a_r)$, где $l \leqslant k \leqslant r; \frac{l}{2} \leqslant k$.
|proof=
Отрезок $(a_{r-k}, a_k)$ содержится в обои операндах правой части. Значит, каждый элемент из него входит два раза. По коммутативности мы можем расположить повторяющиеся располагать элементы друг с другом. По ассоциотивности в любом порядке, по ассоциативности мы можем расставлять скобки как угодновыполнять операции в произвольном порядке, поэтому повторяющие в том числе, обособляя эти самые повторы. А за счет правой части элементы мы можем расположить рядом друг с другом и затем по идемпотентности мы от один из них избавляемсяубрать. В итоге, Переставляя оставшиеся элементы в правой затем легко получаем выражение в левой части равенства.
}}
</wikitex>
