Изменения

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

|definition = Дано корневое подвешенное дерево <tex>T</tex> c <tex>n</tex> вершинами. Поступают запросы вида <tex>LA(v, k)</tex>, для каждого из которых необходимо

== Наивная реализация и двоичные подъемы Использование Heavy-light декомпозиции ==

Используя обход в глубину посчитаем глубину каждой вершины Этот алгоритм базируется на различных способах [[Heavy-light декомпозиция | декомпозиции дерева ]] (это можно сделать за <tex>O(n)</tex>выберем heavy-light декомпозицию), после чего можем из свойств этого разбиения следует,что подняться на любую высоту из вершины <tex>v</tex> подняться до необходимой глубины вершины <tex>k</tex>,что так же в худшем случае работает мы можем за время <tex>O(\log n)</tex>.Получили алгоритм Данное разбиение можно строить за < <tex>O(n), O(n)</tex> >, где время ответа назапрос можно улучшить до что дает нам алгоритм за <tex>\langle O(\log n)</tex> c помощью [[Метод двоичного подъёма | предподсчета двоичных подъемов]] ,но тогда и время предподсчета в наивной реализации (посчитать подъемы для всех вершин) ухудшится до < <tex>O(n \log n),O(\log n)rangle</tex> >. Альтернативой данным двум алгоритмам является полный предподсчет всех возможных запросов В данном примере поступает запрос LA(v, что соответственно дает нам ассимптотику < <tex>O(n^2), O(1)</tex> >на который алгоритм должен дать ответ h.

=== Longest path decomposition <ref>[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]</ref>===Разобьем все Это декомпозиция дерева, которая разбивает его на множество вершинно-непересекающихся путей, идущих из каждой вершины на пути в ее ребенка с самым глубоким поддеревом.Сделаем ее следующим образом. Обойдем : обойдем дерево с помощью обхода в глубину, пусть мы стоим в вершине

т.е. в котором находится вершина с саомй самой большой глубиной.

 ===Ladder decomposition===Увеличим Это улучшение Longest-path декомпозиции, позволяющее, как мы потом докажем, подниматься на любую высоту за <tex>O(1)</tex>. Выполним его следующим образом: увеличим каждый путь в два раза вверх, для каждого ового нового пути сохраним все входящие в него вершины,

нас <tex>O(n) </tex> времени (обход в глубину), соответственно удлиннение каждого пути ухудшит ассимптотику асимптотику до <tex>O(n \log n)</tex>. После этого посчитаем двоичные подьемы подъемы для каждой вершины за <tex>O(\log n)</tex>, что соответственно не ухудшит ассимптотикуасимптотику. === Псевдокод === Пусть после этого нам пришел запрос LA(v, k). *<tex>p[i] [v]</tex> — <tex>i</tex>-тый двоичный подъем в предка вершины <tex>v</tex>*<tex>way[v]</tex> — путь, проходящий через данную вершину*<tex>num[v]</tex> — номер данной вершины на пути*<tex>ladder[p][i]</tex> — возвращает <tex>i</tex>-тую вершину на пути <tex>p</tex>  '''function''' LA('''int''' v,'''int''' k): '''int''' n = h(v) ''<font color="green">// получаем глубину вершины <tex>v</tex></font>'' n = n - k; ''<font color="green">// на столько необходимо подняться до ответа</font>'' i = <tex>\lfloor \log_2 n \rfloor</tex> v = p[i][v] ''<font color="green">// делаем максимально большой прыжок вверх</font>'' i = n - i ''<font color="green">// на столько осталось еще подняться</font>'' '''return''' ladder[way[v]][num[v] - i] ''<font color="green">// так как теперь <tex>v</tex> и ответ находятся на одном пути</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>. Таким образом, наш алгоритм работает за <tex>\langle O(n\log n), O(1)\rangle </tex> времени и за <tex>O(n\log n)</tex> памяти. Методом четырех русских данный метод можно улучшить до <tex>\langle O(n), O(1)\rangle </tex> с помощью оптимизации предподсчета. == The Macro-Micro-Tree Algorithm ==В данном разделе мы докажем, что предподсчет предыдущего алгоритма можно улучшить до <tex>O(n)</tex>.Для начала рассмотрим алгоритм <tex>\langle O(L\log n + n), O(1)\rangle </tex>, где <tex>L</tex> это количество листьев.*С помощью обхода в глубину запомним по одному листу в поддереве для каждой вершины*Воспользуемся алгоритмом лестниц, но будем выполнять предподсчет только для листьев.Рассмотрим как можно улучшить данный алгоритм:*Зададим некую функцию <tex>S(n) = \dfrac{1}{4} \log_2 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), O(1)\rangle </tex> времени и за <tex>O(n)</tex> памяти. == Сравнение с другими реализациями ==Используя DFS посчитаем глубину каждой вершины дерева (это можно сделать за <tex>O(n)</tex>), после чего можем из вершины <tex>v</tex> подняться до необходимой глубины вершины <tex>k</tex>,что так же в худшем случае работает за <tex>O(n)</tex>.Получили алгоритм за <tex>\langle O(n), O(n) \rangle</tex> времени и <tex>O(n)</tex> памяти, где время ответа назапрос можно улучшить до <tex>O(\log n)</tex> c помощью [[Метод двоичного подъёма | предподсчета двоичных подъемов]] ,но тогда и время предподсчета в наивной реализации (посчитать подъемы для всех вершин) ухудшится до <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> памяти.

Пусть после этого нам пришел Сравнение различных асимптотик из данной статьи:{| class="wikitable" style="clear:right;" cellpadding="10"|+|-align="center"!| Предподсчет| Ответ на запрос | Память|-align="center"!Обычный подъем до нужного уровня|<tex>LAO(n)</tex>||<tex>O(n)</tex>||<tex>O(n)</tex>|-align="center"!Полный предподсчет|<tex>O(n^2)</tex>||<tex>O(1)</tex>||<tex>O(n^2)</tex>|-align="center"!Двоичные подъемы|<tex>O(n \log n)</tex>||<tex>O(\log n)</tex>||<tex>O(n \log n)</tex>|-align="center"!Декомпозиция|<tex>O(n)</tex>||<tex>O(\log n)</tex>||<tex>O(n)</tex>|-align="center"!Алгоритм лестниц|<tex>O(n \log n)</tex>||<tex>O(1)</tex>||<tex>O(n \log n)</tex>|-align="center"!Macro-Micro-Tree Algorithm|<tex>O(n)</tex>||<tex>O(1)</tex>||<tex>O(v, kn)</tex>|}== См. также == *[[Метод двоичного подъёма]]*[[Heavy-light декомпозиция]]== Примечания ==<references/>== Источники информации ==*[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][[Категория: Алгоритмы и структуры данных]]