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