Изменения

{{Шаблон:Задача|definition == Постановка задачи RMQ ==Дан массив <tex>A[1..N]</tex>. Поступают запросы вида <tex>(i, j)</tex>, на каждый запрос требуется найти минимум в массиве <tex>A</tex>, начиная с позиции <tex>i</tex> и заканчивая позицией <tex>j</tex>.}} 

===Описание===[[Файл:Wiki.PNG|thumb|right|300x160px400x200px|Пример построенного декартового дерева для массива А]]Будем решать задачу 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</tex>, скажем <tex>A[i]</tex>. Если минимальных значений элементов несколько, можно взять любоелюбой.

<br clear="all"> == Доказательство = Корректность ===Мы знаем что:{{Теорема|statement=* Любая вершина дерева всегда имеет меньшее значение, чем её дети. Тогда любой предок <tex>A[RMQ(i], j)</tex> или = <tex>LCA(A[i], A[j])</tex> меньше их самих.* |proof=Положим <tex>w = LCA(A[i], A[j])</tex> ближайший к корню и по п.1 имеет наименьшее значение в своем поддереве. По построению Заметим, это поддерево содержит в частности подмассив что <tex>A[i..j], </tex> и <tex>LCA(A[ij]</tex> не принадлежат одновременно либо правому, либо левому поддереву <tex>w</tex>, A[j])потому как тогда бы соответствующий сын находился на большей глубине, чем <tex>w</tex> находится между , и также являлся предком как <tex>A[i]</tex> , так и <tex>A[j]</tex>. То есть , что противоречит определению <tex>LCA(A[i], A[j])</tex> является . Из этого замечания следует, что <tex>RMQ(i, j).w</tex>== Построение дерева за линейное время ==Пусть дан массив лежит между <tex>A[1..Ni]</tex>. Будем по очереди слева на право добавлять элементы в дерево. Чтобы добавить новое значение и <tex>A[ij]</tex>и, начнем обход из вершины следовательно, принадлежит отрезку <tex>A[i-1..j]</tex> к корню.  По построению мы также знаем, пока не найдем вершину что:# Любая вершина дерева имеет свое значение меньшим либо равным значению её детей.# Поддерево с корнем в <tex>xw</tex>, для которой содержит в себе подмассив <tex>x < A[i..j]</tex>. Тогда правого сына  Суммируя, получаем, что <tex>xw</tex> назначим левым сыном имеет минимальное значение на отрезке, покрывающем <tex>A[i..j]</tex>, а и принадлежит отрезку <tex>A[i..j]</tex> {{---}} правым сыном <tex>x</tex>. Рассмотрим правую ветку дерева, т.е. по которой проходит обход алгоритма. Заметим, что при добавлении нового узла в дерево элементы, по которым только что прошелся алгоритм отправляются налево, т.е. перестают принадлежать правой ветке. Таким образом процедура поиска родителя не сможет выполнится более отсюда <tex>n</tex> раз и итоговая асимптотика алгоритма <tex>ORMQ(ni, j)= w</tex>.}} === Сложность ===Выше описан Существует [[Декартово дерево#Построение декартова дерева|алгоритм построения дерева ]], который строит декартово дерево за <tex>O(n)</tex>.Используя [[Сведение задачи LCA к задаче RMQ | алгоритм построения LCA]], получаем:Препроцессинг препроцессинг для <tex>LCA</tex> {{---}} <tex>O(n)</tex> и ответ на запрос {{---}} <tex>O(1)</tex>.  Нам нужно единожды построить декартово дерево за <tex>O(n)</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)о наименьшем общем предке]]