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

Постановка задачи 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) Ориентируем каждое ребро в дереве [math]T[/math] и добавим обратное к этому ребру. Получим эйлеров граф [math]E.[/math]. Найдем в графе [math]E[/math] эйлеров цикл, записывая в массив глубину посещенных узлов.

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

Сложность

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

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

Запрос

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

См.также

• Метод двоичного подъема
• Решение RMQ с помощью разреженной таблицы
• Алгоритм Фарака-Колтона и Бендера
• Сведение задачи RMQ к задаче LCA

Ссылки

• Наименьший общий предок. Нахождение за O (sqrt (N)) и O (log N) с препроцессингом O (N)