Изменения
добавлен источник
Дан массив <tex>A[1..N]</tex>. Поступают запросы вида <tex>(l, r)</tex>, на каждый запрос требуется найти минимум в массиве <tex>A</tex>, начиная с позиции <tex>l</tex> и заканчивая позицией <tex>r</tex>.
== Разреженная таблица ==
Разреженная таблица — двумерная структура данных <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>.
<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>
== Источники ==
* ''Bender, M.A., Farach-Colton, M. et al.'' '''Lowest common ancestors in trees and directed acyclic graphs'''. — J. Algorithms 57(2) (2005) — с.75–94.
