Изменения

== Алгоритм ==

[[Файл: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>.