54
правки
Изменения
Нет описания правки
== Алгоритм ==
Декартово дерево(Сartesian tree) на массиве <tex>A[1..N]</tex> - это бинарное дерево, рекурсивно определенное следующим образом:
* 1. Корнем дерева является минимальное значение в массиве <tex>АA</tex>,скажем <tex>A[i]</tex>.* 2. Левым поддеревом является декартово дерево на массиве <tex>A[1..i-1]</tex>.* 3. Правым поддеревом является декартово дерево на массиве <tex>A[i+1..N]</tex>.
Построим декартово дерево на массиве <tex>A</tex>. Тогда <tex>RMQ(i, j)</tex> = <tex>LCA(A[i], A[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>}.
== См.также ==
*[[Сведение задачи RMQ LCA к задаче LCARMQ]]
