74
правки
Изменения
Нет описания правки
== Алгоритм ==
===Описание===
[[Файл:Wiki.PNG|thumb|right|300x150px|Пример декартового дерева]]
Для нахождения минимума на отрезке будем использовать информацию о наименьшем общем предке. Для хранения наименьших общих предков будем использовать [[декартово дерево по неявному ключу]].
<br clear="all">
== Доказательство = Корректность ===
{{Теорема
|statement=
}}
=== Сложность ===
Существует [[Декартово дерево#Построение декартова дерева|алгоритм]], который строит декартово дерево за <tex>O(n)</tex>. Используя [[Сведение задачи LCA к задаче RMQ | алгоритм построения LCA]], получаем:
препроцессинг для <tex>LCA</tex> {{---}} <tex>O(n)</tex> и ответ на запрос {{---}} <tex>O(1)</tex>.
