54
правки
Изменения
Новая страница: «== Постановка задачи RMQ == Дан массив <tex>A[1..N]</tex>. Поступают запросы вида <tex>(i, j)</tex>, на каждый …»
== Постановка задачи RMQ ==
Дан массив <tex>A[1..N]</tex>. Поступают запросы вида <tex>(i, j)</tex>, на каждый запрос требуется найти минимум в массиве <tex>A</tex>, начиная с позиции <tex>i</tex> и заканчивая позицией <tex>j</tex>.
== Алгоритм ==
Декартово дерево(Сartesian tree) на массиве <tex>A[1..N]</tex> - это бинарное дерево, рекурсивно определенное следующим образом:
* Корнем дерева является минимальное значение в массиве <tex>А</tex>,скажем <tex>A[i]</tex>.
* Левым поддеревом является декартово дерево на массиве <tex>A[1..i-1]</tex>.
* Правым поддеревом является декартово дерево на массиве <tex>A[i+1..N]</tex>.
Построим декартово дерево на массиве <tex>A</tex>. Тогда <tex>RMQ(i, j)</tex> = <tex>LCA(A[i], A[j])</tex>.
== Доказательство ==
Мы знаем что:
* 1. Любая вершина дерева всегда имеет меньшее значение, чем её дети. Тогда любой предок <tex>A[i]</tex> или <tex>A[j]</tex> меньше их самих.
* 2. Все вершины, которые лежат в дереве на пути от <tex>A[i]</tex> до <tex>A[j]</tex>, а так же их поддеревья образуют подмассив <tex>A[i..j]</tex>(возьмём только правое поддерево у <tex>A[i]</tex> и левое поддерево у <tex>A[j]</tex>). Т.к. всё, что левее <tex>i</tex>-го элемента в массиве, лежит левее <tex>A[i]</tex> в дереве, и всё, что правее <tex>j</tex>-го, лежит правее <tex>A[j]</tex>. A дерево содержит все элементы <tex>A[1..N]</tex>.
* 3. Из всех вершин, определенных в п.2, <tex>LCA(A[i], A[j])</tex> ближайший к корню и по п.1 имеет наименьшее значение в подмассиве <tex>A[i..j]</tex>.
== Сложность ==
Построение дерева наивным алгоритмом <tex>O(n^2)</tex>. Существует алгоритм построение за <tex>O(n)</tex>.
Препроцессинг для <tex>LCA O(n)</tex> и ответ на запрос <tex>O(1)</tex>. В итоге получили <tex>RMQ</tex> {построение <tex>O(n)</tex>, запрос <tex>O(1)</tex>}.
== См.также ==
*[[Сведение задачи RMQ к задаче LCA]]
Дан массив <tex>A[1..N]</tex>. Поступают запросы вида <tex>(i, j)</tex>, на каждый запрос требуется найти минимум в массиве <tex>A</tex>, начиная с позиции <tex>i</tex> и заканчивая позицией <tex>j</tex>.
== Алгоритм ==
Декартово дерево(Сartesian tree) на массиве <tex>A[1..N]</tex> - это бинарное дерево, рекурсивно определенное следующим образом:
* Корнем дерева является минимальное значение в массиве <tex>А</tex>,скажем <tex>A[i]</tex>.
* Левым поддеревом является декартово дерево на массиве <tex>A[1..i-1]</tex>.
* Правым поддеревом является декартово дерево на массиве <tex>A[i+1..N]</tex>.
Построим декартово дерево на массиве <tex>A</tex>. Тогда <tex>RMQ(i, j)</tex> = <tex>LCA(A[i], A[j])</tex>.
== Доказательство ==
Мы знаем что:
* 1. Любая вершина дерева всегда имеет меньшее значение, чем её дети. Тогда любой предок <tex>A[i]</tex> или <tex>A[j]</tex> меньше их самих.
* 2. Все вершины, которые лежат в дереве на пути от <tex>A[i]</tex> до <tex>A[j]</tex>, а так же их поддеревья образуют подмассив <tex>A[i..j]</tex>(возьмём только правое поддерево у <tex>A[i]</tex> и левое поддерево у <tex>A[j]</tex>). Т.к. всё, что левее <tex>i</tex>-го элемента в массиве, лежит левее <tex>A[i]</tex> в дереве, и всё, что правее <tex>j</tex>-го, лежит правее <tex>A[j]</tex>. A дерево содержит все элементы <tex>A[1..N]</tex>.
* 3. Из всех вершин, определенных в п.2, <tex>LCA(A[i], A[j])</tex> ближайший к корню и по п.1 имеет наименьшее значение в подмассиве <tex>A[i..j]</tex>.
== Сложность ==
Построение дерева наивным алгоритмом <tex>O(n^2)</tex>. Существует алгоритм построение за <tex>O(n)</tex>.
Препроцессинг для <tex>LCA O(n)</tex> и ответ на запрос <tex>O(1)</tex>. В итоге получили <tex>RMQ</tex> {построение <tex>O(n)</tex>, запрос <tex>O(1)</tex>}.
== См.также ==
*[[Сведение задачи RMQ к задаче LCA]]
