Изменения
→Алгоритм
Дан массив <tex>A[1..N]</tex>. Поступают запросы вида <tex>(i, j)</tex>, на каждый запрос требуется найти минимум в массиве <tex>A</tex>, начиная с позиции <tex>i</tex> и заканчивая позицией <tex>j</tex>.
== Алгоритм ==
Декартово дерево (англ. ''с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>.
Здесь и далее <tex>A[i]</tex> будет также использоваться для обозначения соответствующей вершины дерева.
Построим декартово дерево на массиве <tex>A</tex>. Тогда <tex>RMQ(i, j)</tex> = <tex>LCA(A[i], A[j])</tex>.
== Доказательство ==
{{Теорема
