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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Доказательство корректности алгоритма)
(Запрос)
Строка 28: Строка 28:
 
Длина массива глубин будет равна <tex>(2 * n - 1),</tex> т.е. дерево отрезков будет построено за <tex>O(n).</tex> Таким образом, препроцессинг работает за <tex>O(n).</tex>
 
Длина массива глубин будет равна <tex>(2 * n - 1),</tex> т.е. дерево отрезков будет построено за <tex>O(n).</tex> Таким образом, препроцессинг работает за <tex>O(n).</tex>
 
=== Запрос ===
 
=== Запрос ===
Время выполнения запроса равно времени запроса минимального элемента на отрезке в дереве отрезков, т.е. <tex>O(log n).</tex>
+
Время выполнения запроса равно времени запроса минимального элемента на отрезке в дереве отрезков, т.е. <tex>O(\log n).</tex>
  
 
== См.также ==
 
== См.также ==

Версия 05:18, 28 марта 2011

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

Определение:
Наименьшим общим предком (least common ancestor) двух узлов [math]u, v[/math] в корневом дереве [math]T[/math] называется узел [math]w,[/math] который среди всех узлов, являющихся предками как узла [math]u,[/math] так и [math]v,[/math] имеет наибольшую глубину.

Пусть дано корневое дерево [math]T.[/math] На вход подаются запросы вида [math](u,\;v),[/math] для каждого запроса требуется найти их наименьшего общего предка.

Алгоритм

Препроцессинг

1) В каждом узле будет храниться глубина узла в корневом дереве [math]T.[/math]

[math]depth(u)= \begin{cases} 0 & u = root(T),\\ depth(v) + 1 & u = son(v). \end{cases}[/math]

2) Запустим обход в глубину из корня, который будет строить список посещений узлов. Глубина текущей вершины добавляется в список при входе в эту вершину, а также после каждого возвращения из её сына.

3) Построим дерево отрезков с операцией взятия минимума на отрезке по полученному списку узлов.

Запрос

Пусть имеется запрос пара узлов [math]u, v.[/math] Обозначим [math]I[u][/math] - индекс ячейки в списке глубин, в которой хранится глубина узла [math]u.[/math] Тогда запрос минимального элемента на отрезке [math][I[u], I[v]][/math] будет равен глубине наименьшего общего предка узлов [math]u, v.[/math]

Доказательство корректности алгоритма

Рассмотрим два узла [math]u, v[/math] корневого дерева [math]T[/math]. Пусть узел [math]w[/math] - наименьший общий предок узлов [math]u, v[/math]. Очевидно, что в поддереве с корнем [math]w[/math] узел [math]w[/math] будет иметь наименьшую глубину. Осталось доказать, что всегда выполняется неравенство [math]I[u] \le I[w] \le I[v][/math]

Сложность

Препроцессинг

Длина массива глубин будет равна [math](2 * n - 1),[/math] т.е. дерево отрезков будет построено за [math]O(n).[/math] Таким образом, препроцессинг работает за [math]O(n).[/math]

Запрос

Время выполнения запроса равно времени запроса минимального элемента на отрезке в дереве отрезков, т.е. [math]O(\log n).[/math]

См.также

Ссылки