Изменения

== Постановка задачи RMQ ==

Дан массив <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</tex>. Тогда <tex>RMQ(i, j)</tex> = <tex>LCA(A[i], A[j])</tex>.

== Доказательство ==

Мы знаем что:

* Любая вершина дерева всегда имеет меньшее значение, чем её дети. Тогда любой предок <tex>A[i]</tex> или <tex>A[j]</tex> меньше их самих.

* <tex>LCA(A[i], A[j])</tex> ближайший к корню и по п.1 имеет наименьшее значение в своем поддереве. По построению, это поддерево содержит в частности подмассив <tex>A[i..j], </tex> и <tex>LCA(A[i], A[j])</tex> находится между <tex>A[i]</tex> и <tex>A[j]</tex>. То есть <tex>LCA(A[i], A[j])</tex> является <tex>RMQ(i, j).</tex>

== Построение дерева за линейное время ==

Пусть дан массив <tex>A[1..N]</tex>. Будем по очереди слева на право добавлять элементы в дерево. Чтобы добавить новое значение <tex>A[i]</tex>, начнем обход из вершины <tex>A[i-1]</tex> к корню, пока не найдем вершину <tex>x</tex>, для которой <tex>x < A[i]</tex>. Тогда правого сына <tex>x</tex> назначим левым сыном <tex>A[i]</tex>, а <tex>A[i]</tex> {{---}} правым сыном <tex>x</tex>. Рассмотрим правую ветку дерева, т.е. по которой проходит обход алгоритма. Заметим, что при добавлении нового узла в дерево элементы, по которым только что прошелся алгоритм отправляются налево, т.е. перестают принадлежать правой ветке. Таким образом процедура поиска родителя не сможет выполнится более <tex>n</tex> раз и итоговая асимптотика алгоритма <tex>O(n)</tex>.