Изменения
Нет описания правки
'''Задача о уровне предка''' — (англ. "Level Ancestor problem") является задачей о превращении данного корневого подвешенного дерева <tex>T </tex> в структуру данных, которая сможет определить предка любого узла на заданном расстоянии от корня дереваэтого узла.
{{Задача
|definition = Дано корневое подвешенное дерево <tex>T</tex> c <tex>n</tex> вершинами. Поступают запросы вида <tex>LA(v, k)</tex>, для каждого из которых необходимо
найти предка вершины <tex>v</tex>, который находится на расстоянии <tex>k</tex> от корня дерева <tex>T</tex>.
}}
== Наивная реализация и двоичные подъемы Использование Heavy-light декомпозиции ==
[[Файл:LevelAncestor.png|200px|thumb|right]]
== Алгоритм лестниц ==
=== 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>===Разобьем все Это декомпозиция дерева, которая разбивает его на множество вершинно-непересекающихся путей, идущих из каждой вершины на пути в ее ребенка с самым глубоким поддеревом.Сделаем ее следующим образом. Обойдем : обойдем дерево с помощью обхода в глубину, пусть мы стоим в вершине
<tex>v</tex>, обойдем всех ее детей, добавив <tex>v</tex> в путь, идущий в самое глубокое поддерево,
т.е. в котором находится вершина с самой большой глубиной.
Для каждой вершины сохраним номер пути в который она входит.
=== Ladder decomposition ===
а для каждой вершины сохраним ее номер в пути, в который она входит. Построение обычной longest-path декомпозиции займет у
нас <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>''
== 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 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> памяти.
Сравнение различных асимптотик из данной статьи:
{| class="wikitable" style="clear:right;" cellpadding="10"
|+
|-align="center"
!
| Предподсчет
| Ответ на запрос
| Память
|-align="center"
!Обычный подъем до нужного уровня
|<tex>O(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(n)</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_problemWikipedia: LA][[Категория: Алгоритмы и структуры данных]]