Level Ancestor problem

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

Задача:

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

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

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

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

Алгоритм лестниц

Longest path decomposition

Это декомпозиция дерева, которая разбивает его на множество вершинно-непересекающихся путей, идущих из каждой вершины в ее ребенка с самым глубоким поддеревом. Сделаем ее следующим образом: обойдем дерево с помощью обхода в глубину, пусть мы стоим в вершине [math]v[/math], обойдем всех ее детей, добавив [math]v[/math] в путь, идущий в самое глубокое поддерево, т.е. в котором находится вершина с самой большой глубиной. Для каждой вершины сохраним номер пути в который она входит.

Ladder decomposition

Это улучшение Longest-path декомпозиции, позволяющее, как мы потом докажем, подниматься на любую высоту за [math]O(1)[/math]. Выполним его следующим образом: увеличим каждый путь в два раза вверх, для каждого нового пути сохраним все входящие в него вершины, а для каждой вершины сохраним ее номер в пути, в который она входит. Построение обычной longest-path декомпозиции займет у нас [math]O(n)[/math] времени (обход в глубину), удлинение каждого пути не ухудшит асимптотику.

После этого посчитаем двоичные подъемы для каждой вершины за [math]O(\log n)[/math], получим итоговую оценку [math]O(n \log n)[/math] на предподсчет.

Псевдокод

Пусть после этого нам пришел запрос LA(v, k).

• [math]p[i] [v][/math] — [math]i[/math]-тый двоичный подъем в предка вершины [math]v[/math]
• [math]way[v][/math] — путь, проходящий через данную вершину
• [math]num[v][/math] — номер данной вершины на пути
• [math]ladder[p][i][/math] — возвращает [math]i[/math]-тую вершину на пути [math]p[/math]

  function LA(int v,int k):
     int n = h(v) // получаем глубину вершины [math]v[/math]
     n = n - k;  // на столько необходимо подняться до ответа
     i = [math]\lfloor \log_2 n \rfloor[/math]
     v = p[i][v]  // делаем максимально большой прыжок вверх
     i = n - [math]2^i[/math]  // на столько осталось еще подняться
     return ladder[way[v]][num[v] - i] // так как теперь [math]v[/math] и ответ находятся на одном пути

Доказательство корректности

Рассмотрим путь, на котором лежит вершина [math]v[/math] до удвоения. Он длины хотя бы [math]2^i[/math], так как мы точно знаем, что существует вершина потомок [math]v[/math], расстояние до которого ровно [math]2^i[/math] (это вершина, из которой мы только что пришли). Значит, после удвоения этот путь стал длины хотя бы [math]2^{i + 1}[/math], причем хотя бы [math]2^i[/math] вершин в нем — предки [math]v[/math]. Это означает, что вершина, которую мы ищем, находится на этом пути (иначе бы мы могли до этого прыгнуть еще на [math]2^i[/math] вверх). Так как мы знаем позицию [math]v[/math] в этом пути, то нужную вершину мы можем найти за [math]O(1)[/math].

Таким образом, наш алгоритм работает за [math]\langle O(n\log n), O(1)\rangle [/math] времени и за [math]O(n\log n)[/math] памяти. Методом четырех русских данный метод можно улучшить до [math]\langle O(n), O(1)\rangle [/math] с помощью оптимизации предподсчета.

The Macro-Micro-Tree Algorithm

В данном разделе мы докажем, что предподсчет предыдущего алгоритма можно улучшить до [math]O(n)[/math]. Для начала рассмотрим алгоритм [math]\langle O(L\log n + n), O(1)\rangle [/math], где [math]L[/math] это количество листьев.

• С помощью обхода в глубину запомним по одному листу в поддереве для каждой вершины
• Воспользуемся алгоритмом лестниц, но будем выполнять предподсчет только для листьев.

Рассмотрим как можно улучшить данный алгоритм:

• Зададим некую функцию [math]S(n) = \dfrac{1}{4} \log_2 n[/math]
• Посчитаем размер поддерева для каждой вершины с помощью обхода в глубину, после чего удалим все вершины размер поддерева которых меньше чем [math]S(n)[/math].
• Забудем на время про удаленные поддеревья, для оставшегося дерева наш алгоритм работает за [math]\langle O(\dfrac{n}{S(n)} \log n + n), O(1)\rangle [/math]. Получаем алгоритм [math]\langle O(n), O(1) \rangle [/math]. Для удаленных поддеревьев же выполним полный предподсчет: таких деревьев не более чем [math]2^{2S(n)}[/math], что дает асимптотику предподсчета [math]O(\sqrt{n} \log^2{n}) = o(n) = O(n)[/math].

В итоге полученный алгоритм действительно работает за [math]\langle O(n), O(1)\rangle [/math] времени и за [math]O(n)[/math] памяти.

Сравнение с другими реализациями

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

Сравнение различных асимптотик из данной статьи:

	Предподсчет	Ответ на запрос	Память
Обычный подъем до нужного уровня	[math]O(n)[/math]	[math]O(n)[/math]	[math]O(n)[/math]
Полный предподсчет	[math]O(n^2)[/math]	[math]O(1)[/math]	[math]O(n^2)[/math]
Двоичные подъемы	[math]O(n \log n)[/math]	[math]O(\log n)[/math]	[math]O(n \log n)[/math]
Декомпозиция	[math]O(n)[/math]	[math]O(\log n)[/math]	[math]O(n)[/math]
Алгоритм лестниц	[math]O(n \log n)[/math]	[math]O(1)[/math]	[math]O(n \log n)[/math]
Macro-Micro-Tree Algorithm	[math]O(n)[/math]	[math]O(1)[/math]	[math]O(n)[/math]

См. также

• Метод двоичного подъёма
• Heavy-light декомпозиция

Источники информации

• Level Ancestor problem simplified Cai Qi
• Wikipedia: LA