Изменения
→Применение к задаче RMQ
== Применение к задаче RMQ ==
[[Файл:SparseTableRMQ.png|right|Решение задачи RMQ на разреженной таблице]]
<div> Предпосчитаем длину для длины отрезка <tex>l</tex> величину <tex>k=\lfloor \log_2l \rfloor</tex>. Это можно сделать за <tex>O(N\log N)</tex> введением функции <tex>fl[l] = k</tex>, для которой верно <tex>fl[1] = 0, fl[x] = fl[\lfloor \frac{x}{2}\rfloor] + 1</tex>.
Пусть теперь дан запрос <tex>(l, r)</tex>. Заметим, что <tex>\min(A[l], A[l+1], ..., A[r]) = \min\left(ST[l][k], ST[r-2^k+1][j]\right)</tex>, где <tex>k = \max \{j| 2^j \le r - l + 1\}</tex>, т.е. логарифм длины запрашиваемого отрезка, округленный вниз. Но эту величину мы уже предпосчитали, поэтому запрос выполняется за <tex>O (1)</tex>.
