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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
(Алгоритм)
Строка 5: Строка 5:
 
== Алгоритм ==
 
== Алгоритм ==
 
[[Файл:Wiki.PNG|thumb|right|300x150px|Пример декартового дерева]]
 
[[Файл:Wiki.PNG|thumb|right|300x150px|Пример декартового дерева]]
Декартово дерево (англ. ''сartesian tree'') по неявному ключу на массиве <tex>A[1..N]</tex> {{---}} это бинарное дерево, допускающее следующее рекурсивное построение:
+
[[Декартово дерево по неявному ключу]] на массиве <tex>A[1..N]</tex> {{---}} это бинарное дерево, допускающее следующее рекурсивное построение:
 
* Корнем дерева является элемент массива, имеющий минимальное значение <tex>A</tex>, скажем <tex>A[i]</tex>. Если минимальных элементов несколько, можно взять любой.
 
* Корнем дерева является элемент массива, имеющий минимальное значение <tex>A</tex>, скажем <tex>A[i]</tex>. Если минимальных элементов несколько, можно взять любой.
 
* Левым поддеревом является декартово дерево на массиве <tex>A[1..i-1]</tex>.
 
* Левым поддеревом является декартово дерево на массиве <tex>A[1..i-1]</tex>.
Строка 14: Строка 14:
 
Построим декартово дерево на массиве <tex>A</tex>. Тогда <tex>RMQ(i, j)</tex> = <tex>LCA(A[i], A[j])</tex>.
 
Построим декартово дерево на массиве <tex>A</tex>. Тогда <tex>RMQ(i, j)</tex> = <tex>LCA(A[i], A[j])</tex>.
 
<br clear="all">
 
<br clear="all">
 +
 
== Доказательство ==
 
== Доказательство ==
 
{{Теорема
 
{{Теорема

Версия 13:09, 4 июня 2015

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


Алгоритм

Пример декартового дерева

Декартово дерево по неявному ключу на массиве [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[i][/math] будет также использоваться для обозначения соответствующей вершины дерева.

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

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

Теорема:
[math]RMQ(i, j)[/math] = [math]LCA(A[i], A[j])[/math].
Доказательство:
[math]\triangleright[/math]

Положим [math]w = LCA(A[i], A[j])[/math].

Заметим, что [math]A[i][/math] и [math]A[j][/math] не принадлежат одновременно либо правому, либо левому поддереву [math]w[/math], потому как тогда бы соответствующий сын находился на большей глубине, чем [math]w[/math], и также являлся предком как [math]A[i][/math] так и [math]A[j][/math], что противоречит определению [math]LCA[/math]. Из этого замечанию следует, что [math]w[/math] лежит между [math]A[i][/math] и [math]A[j][/math] и, следовательно, принадлежит отрезку [math]A[i..j][/math].


По построению мы также знаем, что:

  1. Любая вершина дерева имеет свое значение меньшим либо равным значению её детей.
  2. Поддерево с корнем в [math]w[/math] содержит в себе подмассив [math]A[i..j][/math].
Суммируя, получаем, что [math]w[/math] имеет минимальное значение на отрезке, покрывающем [math]A[i..j][/math], и принадлежит отрезку [math]A[i..j][/math], отсюда [math]RMQ(i, j) = w[/math].
[math]\triangleleft[/math]

Сложность

Следующий алгоритм строит декартово дерево за [math]O(n)[/math]. Используя Сведение задачи LCA к задаче RMQ, получаем: препроцессинг для [math]LCA[/math][math]O(n)[/math] и ответ на запрос — [math]O(1)[/math]. В итоге получили [math]RMQ[/math] с построением за [math]O(n)[/math] и ответом на запрос за [math]O(1)[/math].

См.также