Сведение задачи RMQ к задаче LCA — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 11: Строка 11:
 
Мы знаем что:
 
Мы знаем что:
 
* 1. Любая вершина дерева всегда имеет меньшее значение, чем её дети. Тогда любой предок <tex>A[i]</tex> или <tex>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>.
+
* 2. <tex>LCA(A[i], A[j])</tex> ближайший к корню и по п.1 имеет наименьшее значение в своем поддереве. По построению, это поддерево содержит как минимум подмассив <tex>A[i..j].</tex> То есть <tex>LCA(A[i], A[j])</tex> является <tex>RMQ(i, j).</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>O(n^2)</tex>. Существует алгоритм построения за <tex>O(n)</tex>.

Версия 21:24, 10 мая 2011

Постановка задачи RMQ

Дан массив [math]A[1..N][/math]. Поступают запросы вида [math](i, j)[/math], на каждый запрос требуется найти минимум в массиве [math]A[/math], начиная с позиции [math]i[/math] и заканчивая позицией [math]j[/math].

Алгоритм

Пример построенного дерева для массива А

Декартово дерево (Сartesian tree) на массиве [math]A[1..N][/math] - это бинарное дерево, рекурсивно определенное следующим образом:

  • Корнем дерева является минимальное значение в массиве [math]A[/math], скажем [math]A[i][/math].
  • Левым поддеревом является декартово дерево на массиве [math]A[1..i-1][/math].
  • Правым поддеревом является декартово дерево на массиве [math]A[i+1..N][/math].

Построим декартово дерево на массиве [math]A[/math]. Тогда [math]RMQ(i, j)[/math] = [math]LCA(A[i], A[j])[/math].

Доказательство

Мы знаем что:

  • 1. Любая вершина дерева всегда имеет меньшее значение, чем её дети. Тогда любой предок [math]A[i][/math] или [math]A[j][/math] меньше их самих.
  • 2. [math]LCA(A[i], A[j])[/math] ближайший к корню и по п.1 имеет наименьшее значение в своем поддереве. По построению, это поддерево содержит как минимум подмассив [math]A[i..j].[/math] То есть [math]LCA(A[i], A[j])[/math] является [math]RMQ(i, j).[/math]

Сложность

Построение дерева наивным алгоритмом [math]O(n^2)[/math]. Существует алгоритм построения за [math]O(n)[/math].

Препроцессинг для [math]LCA[/math] - [math]O(n)[/math] и ответ на запрос [math]O(1)[/math]. В итоге получили [math]RMQ[/math] {построение [math]O(n)[/math], запрос [math]O(1)[/math]}.

См.также

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Сведение_задачи_RMQ_к_задаче_LCA&oldid=8553»