Сведение задачи LCA к задаче RMQ
Постановка задачи LCA
| Определение: |
| Наименьшим общим предком (least common ancestor) двух узлов в корневом дереве называется узел который среди всех узлов, являющихся предками как узла так и имеет наибольшую глубину. |
Пусть дано корневое дерево На вход подаются запросы вида для каждого запроса требуется найти их наименьшего общего предка.
Алгоритм
Препроцессинг
1) В каждом узле будет храниться глубина узла в корневом дереве
2) Запустим обход в глубину из корня, который будет строить список посещений узлов. Глубина текущей вершины добавляется в список при входе в эту вершину, а также после каждого возвращения из её сына.
Запрос
Пусть имеется запрос пара узлов Обозначим - индекс ячейки в списке глубин, в которой хранится глубина узла В результате получился список глубин вершин, в котором наименьшему общему предку вершин соответствует минимальная глубина на отрезке .
Доказательство корректности алгоритма
Рассмотрим два узла корневого дерева . Пусть узел - наименьший общий предок узлов Очевидно, что в поддереве с корнем узел будет иметь наименьшую глубину. Осталось доказать, что всегда выполняется неравенство Пусть вершина посещается раньше, чем вершина Тогда, если вершина не явлется потомком вершины будет выполняться неравенство (так как после посещения поддерева, содержащего вершину , в список будет добавлена вершина , а после - вершина ). А если вершина является предком вершины то вершина будет наименьшим общим предком вершин . Очевидно, что неравенство выполняется.
Пример
Список глубин, получающийся в результате обхода в глубину -
Сложность
Для нахождения минимального элемента на отрезке можно использовать дерево отрезков. Длина массива глубин будет равна т.е. дерево отрезков будет построено за Таким образом, препроцессинг работает за Время выполнения запроса равно времени запроса минимального элемента на отрезке в дереве отрезков, т.е.
