Изменения

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

Разобьем все вершины на пути следующим образом. Обойдем дерево с помощью обхода в глубину, пусть мы стоим в вершине

<tex>v</tex>, обойдем всех ее детей, добавив <tex>v</tex> в путь, идущий в самое глубокое поддерево,

'''int''' n = h(v); ''<font color="green">// получаем глубину вершины <tex>v</tex></font>''

n = n - k; ''<font color="green">// на столько необходимо подняться до ответа</font>''

v = p_i[v] ''<font color="green">// делаем максимально большой прыжок вверх</font>''

i = n - i; ''<font color="green">// на столько осталось еще подняться</font>''

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

== The Macro-Micro-Tree Algorithm ==

В данном разделе мы докажем, что предподсчет предыдущего алгоритма можно улучшить до <tex>O(n)</tex>.

*Воспользуемся алгоритмом лестниц, но будем выполнять предподсчет только для листьев.

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

*Посчитаем размер поддерева для каждой вершины с помощью обхода в глубину, после чего удалим все вершины размер поддерева которых меньше чем <tex>S(n)</tex>.

*Забудем на время про удаленные поддеревья, для оставшегося дерева наш алгоритм работает за <tex>\langle O(\dfrac{n}{S(n)} \log n + n), O(1)\rangle </tex>. Получаем алгоритм <tex>\langle O(n), O(1) \rangle </tex>. Для удаленных поддеревьев же выполним полный предподсчет: таких деревьев не более чем <tex>2^{2S(n)}</tex>, что дает асимптотику предподсчета <tex>O(\sqrt{n} \log^2{n}) = o(n) = O(n)</tex>.

но тогда и время предподсчета в наивной реализации (посчитать подъемы для всех вершин) ухудшится до <tex>\langle O(n \log n),

O(\log n)\rangle </tex> времени и <tex>O(n \log n)</tex> памяти. Также альтернативой данным двум алгоритмам является полный предподсчет всех возможных запросов, что соответственно дает нам асимптотику <tex>\langle O(n^2), O(1)\rangle </tex>времени и <tex>O(n^2)</tex> памяти.

== См. также ==

*[[Метод двоичного подъёма]]