Сведение задачи 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] для каждого запроса требуется найти их наименьшего общего предка.


См.также