78
правок
Изменения
→Разреженная таблица
Иначе говоря, в этой таблице хранятся минимумы на всех отрезках, длины которых равны степеням двойки. Объём памяти, занимаемый таблицей, равен <tex>O(N \log N)</tex>, и заполненными являются только те элементы, для которых <tex>i+2^j \leqslant N </tex>.
Простой метод построения таблицы заключён в следующем реккурентном соотношении: <wikitex>$$ST[i][j]=
\begin{cases}
\min\left(ST[i][j-1], ST[i+2^{j-1}][j-1]\right),&\text{если $j > 0$;}\\
\end{cases}
$$
== Идемпотентность ==
Такая простота достигается за счет идемпотентности операции минимум: <tex>\min(a, a)=a</tex>. Это один из ключевых моментов этого метода, так как она позволяет нам корректно считать минимум в области пересечения отрезков.
