Изменения
Нет описания правки
}}
== Использование Heavy-light декомпозиции ==
[[Файл:LevelAncestor.png|200px|thumb|right]]
Этот алгоритм базируется на различных способах [[Heavy-light декомпозиция | декомпозиции дерева]] (выберем heavy-light декомпозицию), из свойств этого разбиения следует,
что подняться на любую высоту из вершины <tex>v</tex> мы можем за время <tex>O(\log n)</tex>.
== Алгоритм лестниц ==
=== [https://www.mi.fu-berlin.de/en/inf/groups/abi/teaching/lectures/lectures_past/WS0910/V____Discrete_Mathematics_for_Bioinformatics__P1/material/scripts/treedecomposition1.pdf Longest path decomposition ] ===
Разобьем все вершины на пути следующим образом. Обойдем дерево с помощью обхода в глубину, пусть мы стоим в вершине
<tex>v</tex>, обойдем всех ее детей, добавив <tex>v</tex> в путь, идущий в самое глубокое поддерево,
В итоге полученный алгоритм действительно работает за < <tex>O(n), O(1)</tex> > времени и за <tex>O(n)</tex> памяти.
== Сравнение с наивными реализациями ==
что так же в худшем случае работает за <tex>O(n)</tex>.
Получили алгоритм за < <tex>O(n), O(n)</tex> > времени и <tex>O(n)</tex> памяти, где время ответа на
запрос можно улучшить до <tex>O(\log n)</tex> c помощью [[Метод двоичного подъёма | предподсчета двоичных подъемов]] ,
но тогда и время предподсчета в наивной реализации (посчитать подъемы для всех вершин) ухудшится до < <tex>O(n \log n),
O(\log n)</tex> > времени и <tex>O(n \log n)</tex> памяти. Альтернативой Также альтернативой данным двум алгоритмам является полный предподсчет всех возможных запросов, что соответственно дает нам асимптотику < <tex>O(n^2), O(1)</tex> > времени и <tex>O(n^2)</tex> памяти.
Таким образом , самым оптимальным из описанных как по времени, так и по памяти является алгоритм Macro-Micro-Tree.
== См. также ==
*[[Метод двоичного подъёма]]
*[https://www.cadmo.ethz.ch/education/lectures/HS18/SAADS/reports/5.pdf Level Ancestor problem simplified Cai Qi]
*[https://en.wikipedia.org/wiki/Level_ancestor_problem Wikipedia: LA]
*[https://www.mi.fu-berlin.de/en/inf/groups/abi/teaching/lectures/lectures_past/WS0910/V____Discrete_Mathematics_for_Bioinformatics__P1/material/scripts/treedecomposition1.pdf Longest path decomposition]
[[Категория: Алгоритмы и структуры данных]]
