74
правки
Изменения
→Алгоритм
== Алгоритм ==
[[Файл:Wiki.PNG|thumb|right|300x150px|Пример декартового дерева]]
[[Декартово дерево (англ. ''с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">
== Доказательство ==
{{Теорема
