355
правок
Изменения
Нет описания правки
Заметим, что <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]]
== Источники ==
* ''Bender, M.A., Farach-Colton, M. et al.'' — '''Lowest common ancestors in trees and directed acyclic graphs'''. — J. Algorithms 57(2) (2005) — с. 75–94.
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Задача о наименьшем общем предке]]