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