Изменения

{{Шаблон:Задача|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=* 1. Любая вершина дерева всегда имеет меньшее значение<tex>RMQ(i, чем её дети. Тогда любой предок j)</tex> = <tex>LCA(A[i], A[j])</tex> или .|proof=Положим <tex>w = LCA(A[i], A[j])</tex> меньше их самих.* 2. Все вершиныЗаметим, которые лежат в дереве на пути от что <tex>A[i]</tex> до и <tex>A[j]</tex>не принадлежат одновременно либо правому, а так же их поддеревья образуют подмассив либо левому поддереву <tex>w</tex>, потому как тогда бы соответствующий сын находился на большей глубине, чем <tex>A[i..j]w</tex> (возьмём только правое поддерево у , и также являлся предком как <tex>A[i]</tex> , так и левое поддерево у <tex>A[j]</tex>), что противоречит определению <tex>LCA</tex>. Т.к. всёИз этого замечания следует, что левее <tex>iw</tex>-го элемента в массиве, лежит левее между <tex>A[i]</tex> в дереве, и всё, что правее <tex>A[j]</tex>-гои, следовательно, лежит правее принадлежит отрезку <tex>A[i..j]</tex>. A дерево   По построению мы также знаем, что:# Любая вершина дерева имеет свое значение меньшим либо равным значению её детей.# Поддерево с корнем в <tex>w</tex> содержит все элементы в себе подмассив <tex>A[1i..Nj]</tex>.* 3. Из всех вершинСуммируя, получаем, определенных в п.2что <tex>w</tex> имеет минимальное значение на отрезке, покрывающем <tex>LCA(A[i], A[..j])</tex> ближайший к корню , и по п.1 имеет наименьшее значение в подмассиве принадлежит отрезку <tex>A[i..j]</tex>, отсюда <tex>RMQ(i, j) = w</tex>.}} === Сложность ===Существует [[Декартово дерево#Построение декартова дерева наивным алгоритмом |алгоритм]], который строит декартово дерево за <tex>O(n^2)</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>.