Изменения

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

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

102 байта добавлено, 15:53, 8 апреля 2012
Нет описания правки
[[Файл:Wiki.PNG|thumb|right|300x160px|Пример построенного дерева для массива А]]
Декартово дерево (англ. ''сartesian tree'') на массиве <tex>A[1..N]</tex> {{---}} это бинарное дерево, рекурсивно определенное следующим образом:
* Корнем дерева является минимальное значение в массиве <tex>A</tex>, скажем <tex>A[i]</tex>. Если минимальных значений несколько, можно взять любое.
* Левым поддеревом является декартово дерево на массиве <tex>A[1..i-1]</tex>.
* Правым поддеревом является декартово дерево на массиве <tex>A[i+1..N]</tex>.
Анонимный участник

Навигация