Изменения

Перейти к: навигация, поиск

Сведение задачи RMQ к задаче LCA

9 байт убрано, 06:29, 6 мая 2011
Нет описания правки
== Алгоритм ==
Декартово дерево(С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>.
== Доказательство ==
54
правки

Навигация