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

Level Ancestor problem

2019-05-06T19:39:36Z

91.108.28.38:

'''Задача о уровне предка''' (англ. "Level Ancestor problem") является задачей о превращении данного корневого дерева T в структуру данных, которая сможет определить предка любого узла на заданном расстоянии от корня дерева.
{{Задача
|definition = Дано корневое дерево <tex>T</tex> c <tex>n</tex> вершинами. Поступают запросы вида <tex>(v, k)</tex>, для каждого из которых необходимо найти предка вершины <tex>v</tex>, который находится на расстоянии <tex>k</tex> от корня дерева <tex>T</tex>.
}}
== Наивная реализация ==
Используя обход в глубину посчитаем глубину каждой вершины дерева (это можно сделать за <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>.
== Лестничный алгоритм ==
Этот алгоритм базируется на различных способах [[Heavy-light декомпозиция | декомпозиции дерева]] (выберем heavy-light декомпозицию), из свойств этого разбиения следует, что подняться на любую высоту из вершины <tex>v</tex> мы можем за <tex>O(\log n)</tex>. Данное разбиение можно строить за <tex>O(n)</tex>, что дает нам алгоритм за <tex><O(n), O(\log n)></tex>.
== Алгоритм за <tex><O(n), O(1)></tex> ==

Level Ancestor problem

2019-05-06T19:30:54Z

91.108.28.38:

'''Задача о уровне предка''' (англ. "Level Ancestor problem") является задачей о превращении данного корневого дерева T в структуру данных, которая сможет определить предка любого узла на заданном расстоянии от корня дерева.
{{Задача
|definition = Дано корневое дерево <tex>T</tex> c <tex>n</tex> вершинами. Поступают запросы вида <tex>(v, k)</tex>, для каждого из которых необходимо найти предка вершины <tex>v</tex>, который находится на расстоянии <tex>k</tex> от корня дерева <tex>T</tex>.
}}
== Наивная реализация ==
Используя обход в глубину посчитаем глубину каждой вершины дерева (это можно сделать за <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>.
== Лестничный алгоритм ==
Этот алгоритм базируется на различных способах [[Heavy-light декомпозиция | декомпозиции дерева]](выберем heavy-light декомпозицию), из свойств этого разбиения следует, что подняться на любую высоту из вершины <tex>v</tex> мы можем за <tex>O(\log n)</tex>. Данное разбиение можно строить за <tex>O(n)</tex>, что дает нам алгоритм за <tex><O(n), O(\log n)></tex>.

Level Ancestor problem

2019-05-06T18:55:43Z

91.108.28.38:

'''Задача о уровне предка''' (англ. "Level Ancestor problem") является задачей о превращении данного корневого дерева T в структуру данных, которая сможет определить предка любого узла на заданном расстоянии от корня дерева.
{{Задача
|definition = Дано корневое дерево <tex>T</tex> c <tex>n</tex> вершинами. Поступают запросы вида <tex>(v, k)</tex>, для каждого из которых необходимо найти предка вершины <tex>v</tex>, который находится на расстоянии <tex>k</tex> от корня дерева <tex>T</tex>.
}}
== Наивная реализация ==
Используя обход в глубину посчитаем глубину каждой вершины дерева (это можно сделать за <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>.
== Лестничный алгоритм ==

Level Ancestor problem

2019-05-06T18:54:17Z

91.108.28.38:

'''Задача о уровне предка''' - (англ. "Level Ancestor problem") является задачей о превращении данного корневого дерева T в структуру данных, которая сможет определить предка любого узла на заданном расстоянии от корня дерева.
{{Задача
|definition = Дано корневое дерево <tex>T</tex> c <tex>n</tex> вершинами. Поступают запросы вида <tex>(v, k)</tex>, для каждого из которых необходимо найти предка вершины <tex>v</tex>, который находится на расстоянии <tex>k</tex> от корня дерева <tex>T</tex>.
}}
== Наивная реализация ==
Используя обход в глубину посчитаем глубину каждой вершины дерева (это можно сделать за <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>.
== Лестничный алгоритм ==