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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 12: Строка 12:
 
* Любая вершина дерева всегда имеет меньшее значение, чем её дети. Тогда любой предок <tex>A[i]</tex> или <tex>A[j]</tex> меньше их самих.
 
* Любая вершина дерева всегда имеет меньшее значение, чем её дети. Тогда любой предок <tex>A[i]</tex> или <tex>A[j]</tex> меньше их самих.
 
* <tex>LCA(A[i], A[j])</tex> ближайший к корню и по п.1 имеет наименьшее значение в своем поддереве. По построению, это поддерево содержит в частности подмассив <tex>A[i..j], </tex> и <tex>LCA(A[i], A[j])</tex> находится между <tex>A[i]</tex> и  <tex>A[j]</tex>. То есть <tex>LCA(A[i], A[j])</tex> является <tex>RMQ(i, j).</tex>
 
* <tex>LCA(A[i], A[j])</tex> ближайший к корню и по п.1 имеет наименьшее значение в своем поддереве. По построению, это поддерево содержит в частности подмассив <tex>A[i..j], </tex> и <tex>LCA(A[i], A[j])</tex> находится между <tex>A[i]</tex> и  <tex>A[j]</tex>. То есть <tex>LCA(A[i], A[j])</tex> является <tex>RMQ(i, j).</tex>
 +
== Построение дерева за линейное время ==
 +
Пусть дан массив <tex>A[1..N]</tex>. Будем по очереди слева на право добавлять элементы в дерево. Чтобы добавить новое значение <tex>A[i]</tex>, начнем обход из вершины <tex>A[i-1]</tex> к корню, пока не найдем вершину <tex>x</tex>, для которой <tex>x < A[i]</tex>. Тогда правого сына <tex>x</tex> назначим левым сыном <tex>A[i]</tex>, а <tex>A[i]</tex> {{---}} правым сыном <tex>x</tex>. Рассмотрим правую ветку дерева, т.е. по которой проходит обход алгоритма. Заметим, что при добавлении нового узла в дерево элементы, по которым только что прошелся алгоритм отправляются налево, т.е. перестают принадлежать правой ветке. Таким образом процедура поиска родителя не сможет выполнится более <tex>n</tex> раз и итоговая асимптотика алгоритма <tex>O(n)</tex>.
 
== Сложность ==
 
== Сложность ==
Построение дерева наивным алгоритмом <tex>O(n^2)</tex>. Существует алгоритм построения за <tex>O(n)</tex>.
+
Выше описан алгоритм построения дерева за <tex>O(n)</tex>.
 
 
 
Препроцессинг для <tex>LCA</tex> {{---}} <tex>O(n)</tex> и ответ на запрос <tex>O(1)</tex>.  
 
Препроцессинг для <tex>LCA</tex> {{---}} <tex>O(n)</tex> и ответ на запрос <tex>O(1)</tex>.  
 
В итоге получили <tex>RMQ</tex> {построение <tex>O(n)</tex>, запрос <tex>O(1)</tex>}.
 
В итоге получили <tex>RMQ</tex> {построение <tex>O(n)</tex>, запрос <tex>O(1)</tex>}.
 
== См.также ==
 
== См.также ==
 
*[[Сведение задачи LCA к задаче RMQ]]
 
*[[Сведение задачи LCA к задаче RMQ]]
 +
==Ссылки==
 +
*[[http://e-maxx.ru/algo/rmq_linear|Задача RMQ. Решение за O (1) с препроцессингом O (N)]]

Версия 17:04, 8 апреля 2012

Постановка задачи 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].

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

Мы знаем что:

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

Построение дерева за линейное время

Пусть дан массив [math]A[1..N][/math]. Будем по очереди слева на право добавлять элементы в дерево. Чтобы добавить новое значение [math]A[i][/math], начнем обход из вершины [math]A[i-1][/math] к корню, пока не найдем вершину [math]x[/math], для которой [math]x \lt A[i][/math]. Тогда правого сына [math]x[/math] назначим левым сыном [math]A[i][/math], а [math]A[i][/math] — правым сыном [math]x[/math]. Рассмотрим правую ветку дерева, т.е. по которой проходит обход алгоритма. Заметим, что при добавлении нового узла в дерево элементы, по которым только что прошелся алгоритм отправляются налево, т.е. перестают принадлежать правой ветке. Таким образом процедура поиска родителя не сможет выполнится более [math]n[/math] раз и итоговая асимптотика алгоритма [math]O(n)[/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]}.

См.также

Ссылки