53
правки
Изменения
м
Нет описания правки
== Алгоритм ==
[[Файл:Wiki.PNG|thumb|right|300x160px|Пример построенного дерева для массива А]]
Декартово дерево (Сartesian англ. ''сartesian tree'') на массиве <tex>A[1..N]</tex> {{--- }} это бинарное дерево, рекурсивно определенное следующим образом:
* Корнем дерева является минимальное значение в массиве <tex>A</tex>, скажем <tex>A[i]</tex>.
* Левым поддеревом является декартово дерево на массиве <tex>A[1..i-1]</tex>.
== Доказательство ==
Мы знаем что:
* 1. Любая вершина дерева всегда имеет меньшее значение, чем её дети. Тогда любой предок <tex>A[i]</tex> или <tex>A[j]</tex> меньше их самих.* 2. <tex>LCA(A[i], A[j])</tex> ближайший к корню и по п.1 имеет наименьшее значение в своем поддереве. По построению, это поддерево содержит в частности подмассив <tex>A[i..j], </tex> и <tex>LCA(A[i], A[j])</tex> находится между <tex>A[i]</tex> и <tex>A[j]</tex>. То есть <tex>LCA(A[i], A[j])</tex> является <tex>RMQ(i, j).</tex>
== Сложность ==
Построение дерева наивным алгоритмом <tex>O(n^2)</tex>. Существует алгоритм построения за <tex>O(n)</tex>.
Препроцессинг для <tex>LCA</tex> {{- --}} <tex>O(n)</tex> и ответ на запрос <tex>O(1)</tex>.
В итоге получили <tex>RMQ</tex> {построение <tex>O(n)</tex>, запрос <tex>O(1)</tex>}.
== См.также ==
*[[Сведение задачи LCA к задаче RMQ]]
