53
правки
Изменения
Нет описания правки
'''Разреженная таблица ''' (англ. ''sparse table'') позволяет решать задачу online static RMQ за <tex>O(1)</tex> на запрос, с предподсчётом за <tex>O(N \log N)</tex> и использованием <tex>O(N \log N)</tex> памяти.
== Постановка задачи RMQ ==
Дан массив <tex>A[1..N]</tex>. Поступают запросы вида <tex>(l, r)</tex>, на каждый запрос требуется найти минимум в массиве <tex>A</tex>, начиная с позиции <tex>l</tex> и заканчивая позицией <tex>r</tex>.
Простой метод построения таблицы заключён в следующем реккурентном соотношении: <tex>ST[i,j]=\min\left(ST[i,j-1], ST[i+2^{j-1}, j-1]\right)</tex>.
== Применение к задаче RMQ ==
[[Файл:SparseTableRMQ.png|right|Решение задачи RMQ на разреженной таблице]]<div>Дан запрос <tex>(l, r)</tex>. По нему найдём <tex>\max j: 2^j \le r - l + 1</tex>, т.е. логарифм длины запрашиваемого отрезка.Заметим, что <tex>\min(A[l], A[l+1], ..., A[r]) = \min\left(ST[l, j], ST[r-2^j+1,j]\right)</tex>. Таким образом, если находить <tex>j</tex> за <tex>O(1)</tex> (например, предподсчётом за <tex>O(N \log N)</tex> для всех возможных длин отрезков), можно отвечать на запрос за константное время.</div>
