355
правок
Изменения
→Разреженная таблица
== Разреженная таблица ==
Разреженная таблица — двумерная структура данных <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>.
Простой метод построения таблицы заключён в следующем реккурентном соотношении:
<texwikitex> $$ST[i][j] = \left\{ \begin{array}{rclcases} \min\left(ST[i][j-1], ST[i+2^{j-1}][j-1]\right), &\text{если $j > 0 $;}\\ A[i], &\text{если $j = 0. \\ $;} \end{arraycases} \right. $$</texwikitex>
=== Идемпотентность ===
Такая простота достигается за счет идемпотентности операции минимум: <tex>\min(a, a)=a</tex>. Это один из ключевых моментов этого метода, так как она позволяет нам корректно считать минимум в области пересечения отрезков.
