Изменения

[[Файл:LevelAncestor.png|120px|thumb|right]]'''Задача о уровне предка''' (англ. "Level Ancestor problem") является задачей о превращении данного корневого дерева T в структуру данных, которая сможет определить предка любого узла на заданном расстоянии от корня дерева.В данном примере поступает запрос <tex>LA(v, 2)</tex>, на который алгоритм должен дать ответ h.

== Наивная реализация реализациb и двоичные подъемы ==[[Файл:Двоичные_подъемыLevelAncestor.png|200px|thumb|right|Двоичные подъемы]]Используя обход в глубину посчитаем глубину каждой вершины дерева (это можно сделать за <tex>O(n)</tex>), после чего можем из вершины <tex>v</tex> подняться до необходимой глубины вершины <tex>k</tex>, что так же в худшем случае работает за <tex>O(n)</tex>. Получили алгоритм за <tex><O(n),O(n)></tex>, где время ответа на запрос можно улучшить до <tex>O(\log n)</tex> c помощью [[Метод двоичного подъёма | предподсчета двоичных подъемов]] , но тогда и время предподсчета в наивной реализации (посчитать подъемы для всех вершин) ухудшится до <tex><O(n \log n),O(\log n)></tex>. Альтернативой данным двум алгоритмам является полный предподсчет всех возможных запросов, что соответственно дает нам алгоритм <tex><O(n^2),O(1)></tex>.В данном примере поступает запрос <tex>LA(v, 2)</tex>, на который алгоритм должен дать ответ h.