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]=\min\left(ST[i,j-1], ST[i+2^{j-1}, j-1]\right)</tex>, что достигается за счет идемпотентности операции минимум: <tex>\min(a, a)=a</tex>.Это один из ключевых моментов этого метода.
== Применение к задаче RMQ ==
[[Файл:SparseTableRMQ.png|right|Решение задачи RMQ на разреженной таблице]]
