74
правки
Изменения
→Алгоритм
== Алгоритм ==
[[Файл:Wiki.PNG|thumb|right|300x150px|Пример декартового дерева]]
Для нахождения минимума на отрезке будем использовать информацию о наименьшем общем предке. Для хранения наименьших общих предков будем использовать [[Декартово декартово дерево по неявному ключу]] . Декартово дерево по неявному ключу на массиве <tex>A[1..N]</tex> {{---}} это бинарное дерево, допускающее следующее рекурсивное построение:
* Корнем дерева является элемент массива, имеющий минимальное значение <tex>A</tex>, скажем <tex>A[i]</tex>. Если минимальных элементов несколько, можно взять любой.
* Левым поддеревом является декартово дерево на массиве <tex>A[1..i-1]</tex>.
