74
правки
Изменения
м
== Постановка задачи RMQ =={{Шаблон:Задача[[Файл:Wiki.PNG|thumb|right|300x160px|Пример построенного дерева для массива А]]definition =Дан массив <tex>A[1..N]</tex>. Поступают запросы вида <tex>(i, j)</tex>, на каждый запрос требуется найти минимум в массиве <tex>A</tex>, начиная с позиции <tex>i</tex> и заканчивая позицией <tex>j</tex>.}}
Нет описания правки
== Алгоритм ==
[[Файл:Wiki.PNG|thumb|right|300x150px|Пример декартового дерева]]
Декартово дерево (англ. ''с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>.
<br clear="all">
== Доказательство ==
{{Теорема
