Изменения

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