Изменения

Заметим, что <tex>\min(A[l], A[l+1], ..., A[r]) = \min\left(ST[l][k], ST[r-2^k+1][j]\right)</tex>. Заметим <tex>k</tex> зависит лишь от длины отрезка. Предпосчитаем эту величину за <tex>O(N\log N)</tex> следующим образом: <tex>fl[x] = fl[\lfloor \frac{x}{2}\rfloor] + 1</tex>. Теперь мы можем находить <tex>k</tex> за <tex>O(1)</tex>. Таким образом, ответ на запрос происходит за константное время.</div>

<div style="clear:both"></div>

== См. также ==

* [[Алгоритм Фарака-Колтона и Бендера | Алгоритм Фарака-Колтона и Бендера]]

* [[Сведение задачи RMQ к задаче LCA | Сведение задачи RMQ к задаче LCA]]

[[Категория: Алгоритмы и структуры данных]]

[[Категория: Задача о наименьшем общем предке]]