Изменения

== Постановка задачи 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|400x200px|Пример декартового дерева]]Будем решать задачу RMQ, уже умея решать задачу LCA. Для хранения решения задачи о LCA будем использовать [[декартово дерево по неявному ключу]]. Тогда минимум на отрезке от <tex> i </tex> до <tex> j </tex> массива <tex> A </tex> будет равен наименьшему общему предку <tex>i</tex>-того и <tex>j</tex>-того элементов из декартова дерева, построенного на массиве <tex> A </tex>.   Декартово дерево (англ. ''сartesian tree'') по неявному ключу на массиве <tex>A[1..N]</tex> {{---}} это бинарное дерево, допускающее следующее рекурсивное построение:

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

Заметим, что <tex>A[i]</tex> и <tex>A[j]</tex> не принадлежат одновременно либо правому, либо левому поддереву <tex>w</tex>, потому как тогда бы соответствующий сын находился на большей глубине, чем <tex>w</tex>, и также являлся предком как <tex>A[i]</tex> , так и <tex>A[j]</tex>, что противоречит определению <tex>LCA</tex>. Из этого замечанию замечания следует, что <tex>w</tex> лежит между <tex>A[i]</tex> и <tex>A[j]</tex> и, следовательно, принадлежит отрезку <tex>A[i..j]</tex>.

== Построение дерева за линейное время = Сложность ===Пусть дан массив <tex>AСуществует [[1..N]</tex>. Будем по очереди слева на право добавлять элементы в Декартово дерево. Чтобы добавить новое значение <tex>A[i#Построение декартова дерева|алгоритм]</tex>, начнем обход из вершины <tex>A[i-1]</tex> к корню, пока не найдем вершину который строит декартово дерево за <tex>xO(n)</tex>, для которой <tex>x < A. Используя [[iСведение задачи LCA к задаче RMQ | алгоритм построения LCA]</tex>. Тогда правого сына <tex>x</tex> назначим левым сыном <tex>A[i]</tex>, а получаем:препроцессинг для <tex>A[i]LCA</tex> {{---}} правым сыном <tex>x</tex>. Рассмотрим правую ветку дерева, т.е. по которой проходит обход алгоритма. Заметим, что при добавлении нового узла в дерево элементы, по которым только что прошелся алгоритм отправляются налево, т.е. перестают принадлежать правой ветке. Таким образом процедура поиска родителя не сможет выполнится более <tex>O(n)</tex> раз и итоговая асимптотика алгоритма ответ на запрос {{---}} <tex>O(n1)</tex>.== Сложность ==Выше описан алгоритм построения дерева Нам нужно единожды построить декартово дерево за <tex>O(n)</tex>.Препроцессинг для <tex>LCA</tex> {{---}} , единожды провести препроцессинг за <tex>O(n)</tex> и ответ отвечать на запрос запросы за <tex>O(1)</tex>.  В итоге получили <tex>RMQ</tex> {построение с построением за <tex>O(n)</tex>, и ответом на запрос за <tex>O(1)</tex>}. 

==Ссылки==*[[Декартово дерево]]*[http[Алгоритм Фарака-Колтона и Бендера]] [[Категория: Алгоритмы и структуры данных]][[Категория://e-maxx.ru/algo/rmq_linear Задача RMQ. Решение за O (1) с препроцессингом O (N)о наименьшем общем предке]]