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