Викиконспекты - Вклад участника [ru]

Level Ancestor problem

2019-05-14T17:04:18Z

91.108.28.12:

'''Задача о уровне предка''' (англ. "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>.
}}
== Наивная реализация и двоичные подъемы ==
[[Файл: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>, на который алгоритм должен дать ответ <tex>h</tex>.

== Использование Heavy-light декомпозиции ==
Этот алгоритм базируется на различных способах [[Heavy-light декомпозиция | декомпозиции дерева]] (выберем heavy-light декомпозицию), из свойств этого разбиения следует,
что подняться на любую высоту из вершины <tex>v</tex> мы можем за время <tex>O(\log n)</tex>.
Данное разбиение можно строить за <tex>O(n)</tex>, что дает нам алгоритм за < <tex>O(n), O(\log n)</tex> >.

== Алгоритм лестниц ==
=== Longest path decomposition ===
Разобьем все вершины на пути следующим образом. Обойдем дерево с помощью обхода в глубину, пусть мы стоим в вершине
<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>, что соответственно не ухудшит асимптотику.

Пусть после этого нам пришел запрос <tex>LA(v, k)</tex>.

*Сделаем один максимально большой прыжок вверх с помощью насчитанных двоичных подъемов.
#<tex>i = \log k</tex>
#<tex>v = p_i[v]</tex>
=== Доказательство корректности ===
Рассмотрим путь, на котором лежит вершина <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>O(n\log n), O(1)</tex> >. Методом четырех русских данный метод можно улучшить до < <tex>O(n), O(1)</tex> > с помощью оптимизации предподсчета.
== The Macro-Micro-Tree Algorithm ==
В данном разделе мы докажем, что предподсчет предыдущего алгоритма можно улучшить до <tex>O(n)</tex>.
Для начала рассмотрим алгоритм < <tex>O(L\log n + n), O(1)</tex> >, где <tex>L</tex> это количество листьев.
*С помощью обхода в глубину запомним по одному листу в ее поддереве для каждой вершины
*Воспользуемся алгоритмом лестниц, но будем выполнять предподсчет только для листьев.
Рассмотрим как можно улучшить данный алгоритм:
*Зададим некую функцию <tex>S(n) = \dfrac{1}{4} \log n</tex>
*Посчитаем размер поддерева для каждой вершины с помощью обхода в глубину, после чего удалим все вершины размер поддерева которых меньше чем <tex>S(n)</tex>.
*Забудем на время про удаленные поддеревья, для оставшегося дерева наш алгоритм работает за < <tex>O(\dfrac{n}{S(n)} \log n + n), O(1)</tex> >. Получаем алгоритм < <tex>O(n), O(1) </tex> >. Для удаленных поддеревьев же выполним полный предподсчет: таких деревьев не более чем <tex>2^{2S(n)}</tex>, что дает асимптотику предподсчета <tex>O(\sqrt{n} \log^2{n}) = o(n) = O(n)</tex>.

В итоге полученный алгоритм действительно работает за < <tex>O(n), O(1)</tex> >.

== Источники информации ==
*https://www.cadmo.ethz.ch/education/lectures/HS18/SAADS/reports/5.pdf
*https://en.wikipedia.org/wiki/Level_ancestor_problem

Level Ancestor problem

2019-05-14T17:03:34Z

91.108.28.12:

'''Задача о уровне предка''' (англ. "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>.
}}
== Наивная реализация и двоичные подъемы ==
[[Файл: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>, на который алгоритм должен дать ответ <tex>h</tex>.

== Использование Heavy-light декомпозиции ==
Этот алгоритм базируется на различных способах [[Heavy-light декомпозиция | декомпозиции дерева]] (выберем heavy-light декомпозицию), из свойств этого разбиения следует,
что подняться на любую высоту из вершины <tex>v</tex> мы можем за время <tex>O(\log n)</tex>.
Данное разбиение можно строить за <tex>O(n)</tex>, что дает нам алгоритм за < <tex>O(n), O(\log n)</tex> >.

== Алгоритм лестниц ==
=== Longest path decomposition ===
Разобьем все вершины на пути следующим образом. Обойдем дерево с помощью обхода в глубину, пусть мы стоим в вершине
<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>, что соответственно не ухудшит асимптотику.

Пусть после этого нам пришел запрос <tex>LA(v, k)</tex>.

*Сделаем один максимально большой прыжок вверх с помощью насчитанных двоичных подъемов.
#<tex>i = \log k</tex>
#<tex>v = p_i[v]</tex>
=== Доказательство корректности ===
* Рассмотрим путь, на котором лежит вершина <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>O(n\log n), O(1)</tex> >. Методом четырех русских данный метод можно улучшить до < <tex>O(n), O(1)</tex> > с помощью оптимизации предподсчета.
== The Macro-Micro-Tree Algorithm ==
В данном разделе мы докажем, что предподсчет предыдущего алгоритма можно улучшить до <tex>O(n)</tex>.
Для начала рассмотрим алгоритм < <tex>O(L\log n + n), O(1)</tex> >, где <tex>L</tex> это количество листьев.
*С помощью обхода в глубину запомним по одному листу в ее поддереве для каждой вершины
*Воспользуемся алгоритмом лестниц, но будем выполнять предподсчет только для листьев.
Рассмотрим как можно улучшить данный алгоритм:
*Зададим некую функцию <tex>S(n) = \dfrac{1}{4} \log n</tex>
*Посчитаем размер поддерева для каждой вершины с помощью обхода в глубину, после чего удалим все вершины размер поддерева которых меньше чем <tex>S(n)</tex>.
*Забудем на время про удаленные поддеревья, для оставшегося дерева наш алгоритм работает за < <tex>O(\dfrac{n}{S(n)} \log n + n), O(1)</tex> >. Получаем алгоритм < <tex>O(n), O(1) </tex> >. Для удаленных поддеревьев же выполним полный предподсчет: таких деревьев не более чем <tex>2^{2S(n)}</tex>, что дает асимптотику предподсчета <tex>O(\sqrt{n} \log^2{n}) = o(n) = O(n)</tex>.

В итоге полученный алгоритм действительно работает за < <tex>O(n), O(1)</tex> >.

== Источники информации ==
*https://www.cadmo.ethz.ch/education/lectures/HS18/SAADS/reports/5.pdf
*https://en.wikipedia.org/wiki/Level_ancestor_problem