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>. Иначе говоря, в этой таблице хранятся минимумы на всех отрезках, длины которых равны степеням двойки. Объём, занимаемый таблицей, равен <tex>O(N \log N)</tex>, и заполненными являются только те элементы, для которых <tex>i+2^j \le N </tex>.
Простой метод построения таблицы заключён в следующем реккурентном соотношении: <tex>ST[i,][j]=\left\{ \begin{array}{lcl} \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>. Это один из ключевых моментов этого метода, так как идемпотентность позволяет нам корректно считать минимум в области пересечения отрезков.
== Применение к задаче RMQ ==
