Изменения
Новая страница: «''Алгоритм Шибера-Вишкина'' применяется для нахождения наименьшего общего предка двух ве...»
''Алгоритм Шибера-Вишкина'' применяется для нахождения наименьшего общего предка двух вершин в дереве.
Он использует <tex>O(n)</tex> времени на подготовку и затем отвечает на каждый запрос за <tex>O(1)</tex>.
==Идея алгоритма==
Основная идея алгоритма следующая.
# Если бы дерево, в котором нужно искать <tex>LCA</tex> было бы цепочкой, можно было бы найти <tex>LCA(u, v)</tex> просто взяв ту вершину, которая находится в дереве выше.
# Если дерево {{---}} полное двоичное дерево высоты <tex>h</tex>, то можно сопоставить каждой вершине битовый вектор длиной <tex>h</tex> (целое число от <tex>0</tex> до <tex>2^h-1</tex>) и с помощью битовых операций над этими векторами найти <tex>LCA(u, v)</tex>
Тогда, представив данное дерево как полное двоичное дерево, в каждой вершине которого находится цепочка, можно
научиться искать <tex>LCA(v, u)</tex> в нем за <tex>O(1)</tex>.
==Подготовка==
Перенумеруем вершины в порядке префиксного обхода дерева: сначала обходится текущая вершина, затем {{---}} поддеревья.
Пусть <tex>\operatorname{order} : V \to \mathbb{N}</tex> {{---}} такой порядок обхода.
Обозначим за <tex>\operatorname{size} v</tex> количество вершин в поддереве вершины <tex>v</tex>. Здесь и далее считаем,
что вершина является и своим предком, и своим потомком.
{{Утверждение
|statement=Пусть <tex>u</tex> {{---}} вершина из поддерева <tex>v</tex>. Тогда
<tex>\operatorname{order} u \in [\operatorname{order} v; \operatorname{order}v + \operatorname{size} v - 1]</tex>
|proof=
По определению <tex>\operatorname{order}</tex>, <tex>\operatorname{order} u</tex> вершин из поддерева <tex>v</tex> образуют
отрезок натуральных чисел длиной <tex>\operatorname{size} v - 1</tex>. Так как этот отрезок начинается с
<tex>\operatorname{order}v + 1</tex>, то <tex>\operatorname{order} u</tex> {{---}} отрезок <tex>[\operatorname{order} v; \operatorname{order} v + \operatorname{size} v - 1]</tex>.
}}
Покроем дерево путями. А именно, сопоставим каждой вершине <tex>v</tex> число <tex>\operatorname{chain} v</tex> такое, что прообраз каждого <tex>\operatorname{chain} v</tex> в <tex>T</tex> связен и является простым путем от какой-то вершины вниз до листа.
{{Утверждение
|statement=В качестве <tex>\operatorname{chain} v</tex> можно выбрать <tex>\operatorname{order} u</tex>, кратное максимальной степени двойки, где <tex>u \in S(v)</tex>.
|proof=?
}}
==Обработка запроса==
Он использует <tex>O(n)</tex> времени на подготовку и затем отвечает на каждый запрос за <tex>O(1)</tex>.
==Идея алгоритма==
Основная идея алгоритма следующая.
# Если бы дерево, в котором нужно искать <tex>LCA</tex> было бы цепочкой, можно было бы найти <tex>LCA(u, v)</tex> просто взяв ту вершину, которая находится в дереве выше.
# Если дерево {{---}} полное двоичное дерево высоты <tex>h</tex>, то можно сопоставить каждой вершине битовый вектор длиной <tex>h</tex> (целое число от <tex>0</tex> до <tex>2^h-1</tex>) и с помощью битовых операций над этими векторами найти <tex>LCA(u, v)</tex>
Тогда, представив данное дерево как полное двоичное дерево, в каждой вершине которого находится цепочка, можно
научиться искать <tex>LCA(v, u)</tex> в нем за <tex>O(1)</tex>.
==Подготовка==
Перенумеруем вершины в порядке префиксного обхода дерева: сначала обходится текущая вершина, затем {{---}} поддеревья.
Пусть <tex>\operatorname{order} : V \to \mathbb{N}</tex> {{---}} такой порядок обхода.
Обозначим за <tex>\operatorname{size} v</tex> количество вершин в поддереве вершины <tex>v</tex>. Здесь и далее считаем,
что вершина является и своим предком, и своим потомком.
{{Утверждение
|statement=Пусть <tex>u</tex> {{---}} вершина из поддерева <tex>v</tex>. Тогда
<tex>\operatorname{order} u \in [\operatorname{order} v; \operatorname{order}v + \operatorname{size} v - 1]</tex>
|proof=
По определению <tex>\operatorname{order}</tex>, <tex>\operatorname{order} u</tex> вершин из поддерева <tex>v</tex> образуют
отрезок натуральных чисел длиной <tex>\operatorname{size} v - 1</tex>. Так как этот отрезок начинается с
<tex>\operatorname{order}v + 1</tex>, то <tex>\operatorname{order} u</tex> {{---}} отрезок <tex>[\operatorname{order} v; \operatorname{order} v + \operatorname{size} v - 1]</tex>.
}}
Покроем дерево путями. А именно, сопоставим каждой вершине <tex>v</tex> число <tex>\operatorname{chain} v</tex> такое, что прообраз каждого <tex>\operatorname{chain} v</tex> в <tex>T</tex> связен и является простым путем от какой-то вершины вниз до листа.
{{Утверждение
|statement=В качестве <tex>\operatorname{chain} v</tex> можно выбрать <tex>\operatorname{order} u</tex>, кратное максимальной степени двойки, где <tex>u \in S(v)</tex>.
|proof=?
}}
==Обработка запроса==
