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

Постановка задачи LCA

Определение:

Наименьший общий предок (least common ancestor) двух узлов [math]u, v[/math] в корневом дереве [math]T[/math] - это такой узел [math]w[/math], который среди всех узлов, являющихся предками как узла [math]u[/math], так и [math]v[/math], имеет наибольшую глубину.

См.также

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