Изменения

Перейти к: навигация, поиск

Сведение задачи LCA к задаче RMQ

111 байт убрано, 04:00, 28 апреля 2011
Алгоритм
2) Запустим обход в глубину из корня, который будет строить список посещений узлов. Глубина текущей вершины добавляется в список при входе в эту вершину, а также после каждого возвращения из её сына.
 
3) Построим дерево отрезков с операцией взятия минимума на отрезке по полученному списку узлов.
=== Запрос ===
Пусть имеется запрос пара узлов <tex>u, v.</tex> Обозначим <tex>I[u]</tex> - индекс ячейки в списке глубин, в которой хранится глубина узла <tex>u.</tex> Тогда запрос минимального элемента В результате получился список глубин вершин, в котором наименьшему общему предку вершин <tex>u, v</tex> соответствует минимальная глубина на отрезке <tex>[I[u], I[v]]</tex> будет равен глубине наименьшего общего предка узлов <tex>u, v.</tex>
== Доказательство корректности алгоритма ==
Анонимный участник

Навигация