Level Ancestor problem

Задача о уровне предка (англ. "Level Ancestor problem") является задачей о превращении данного корневого дерева T в структуру данных, которая сможет определить предка любого узла на заданном расстоянии от корня дерева.

Задача:

Дано корневое дерево [math]T[/math] c [math]n[/math] вершинами. Поступают запросы вида [math]LA(v, k)[/math], для каждого из которых необходимо найти предка вершины [math]v[/math], который находится на расстоянии [math]k[/math] от корня дерева [math]T[/math].

Наивная реализация и двоичные подъемы

Используя обход в глубину посчитаем глубину каждой вершины дерева (это можно сделать за [math]O(n)[/math]), после чего можем из вершины [math]v[/math] подняться до необходимой глубины вершины [math]k[/math], что так же в худшем случае работает за [math]O(n)[/math]. Получили алгоритм за < [math]O(n), O(n)[/math] >, где время ответа на запрос можно улучшить до [math]O(\log n)[/math] c помощью предподсчета двоичных подъемов , но тогда и время предподсчета в наивной реализации (посчитать подъемы для всех вершин) ухудшится до < [math]O(n \log n), O(\log n)[/math] >. Альтернативой данным двум алгоритмам является полный предподсчет всех возможных запросов, что соответственно дает нам ассимптотику < [math]O(n^2), O(1)[/math] >.

В данном примере поступает запрос [math]LA(v, 2)[/math], на который алгоритм должен дать ответ h.

Использование Heavy-light декомпозиции

Этот алгоритм базируется на различных способах декомпозиции дерева (выберем heavy-light декомпозицию), из свойств этого разбиения следует, что подняться на любую высоту из вершины [math]v[/math] мы можем за [math]O(\log n)[/math]. Данное разбиение можно строить за [math]O(n)[/math], что дает нам алгоритм за < [math]O(n), O(\log n)[/math] >.