1
правка
Изменения
Не соблюдены нормы русского языка. Изменил 3 ошибки (одна орфографическая и две пунктуационных).
== Алгоритм ==
===Описание===[[Файл:Wiki.PNG|thumb|right|400x200px|Пример декартового дерева]]Будем решать задачу RMQ, уже умея решать задачу LCA. Для хранения решения задачи о LCA будем использовать [[декартово дерево по неявному ключу]]. Тогда минимум на отрезке от <tex> i </tex> до <tex> j </tex> массива <tex> A </tex> будет равен наименьшему общему предку <tex>i</tex>-того и <tex>j</tex>-того элементов из декартова дерева, построенного на массиве <tex> A </tex>. Декартово дерево (англ. ''сartesian tree'') по неявному ключу на массиве <tex>A[1..N]</tex> {{---}} это бинарное дерево, допускающее следующее рекурсивное построение:
* Корнем дерева является элемент массива, имеющий минимальное значение <tex>A</tex>, скажем <tex>A[i]</tex>. Если минимальных элементов несколько, можно взять любой.
* Левым поддеревом является декартово дерево на массиве <tex>A[1..i-1]</tex>.
Построим декартово дерево на массиве <tex>A</tex>. Тогда <tex>RMQ(i, j)</tex> = <tex>LCA(A[i], A[j])</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>.
== См.также ==
*[[Сведение задачи LCA к задаче RMQ]]
