Изменения
Нет описания правки
''Алгоритм Шибера-Вишкина'' применяется для нахождения [[Сведение задачи LCA к задаче RMQ|наименьшего общего предка]] (англ. ''least common ancestor'') двух вершин в дереве.
Он использует <tex>O(n)</tex> времени на подготовку препроцессинг и затем отвечает на каждый запрос за <tex>O(1)</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>T</tex> {{---}} входное дерево с <tex>n</tex> вершинами. Для него нужно отвечать на запросы <tex>LCA</tex>.<br>
<tex>B</tex> {{---}} полное [[Дерево поиска, наивная реализация|двоичное дерево ]] с не менее, чем <tex>n</tex> вершинами. Будет введено и объяснено дальше.<br>
<tex>u \in S(v)</tex> {{---}} вершина <tex>u</tex> находится в поддереве вершины <tex>v</tex>. Здесь и далее считаем, что вершина является и своим предком, и своим потомком.<br>
<tex>v</tex> ''выше'' <tex>u</tex> {{---}} то же самое, что <tex>u \in S(v)</tex>. Корень выше любой вершины.
Перенумеруем вершины в порядке префиксного обхода дерева: сначала обрабатывается текущая вершина, затем {{---}} поддеревья.
Пусть <tex>\operatorname{pre-order} : V \to \mathbb{N}</tex> {{---}} такой порядок обхода.
Обозначим за <tex>\operatorname{size} v</tex> количество вершин в поддереве вершины <tex>v</tex>.
{{Утверждение
|statement=Пусть <tex>u \in S(v)</tex>. Тогда
<tex>\operatorname{pre-order} u \in [\operatorname{pre-order} v; \operatorname{pre-order}v + \operatorname{size} v - 1]</tex>
|proof=
По определению <tex>\operatorname{pre-order}</tex>, <tex>\operatorname{pre-order} u</tex> вершин из поддерева <tex>v</tex> образуют
отрезок натуральных чисел длиной <tex>\operatorname{size} v - 1</tex>. Так как этот отрезок начинается с
<tex>\operatorname{pre-order}v + 1</tex>, то <tex>\operatorname{pre-order} u</tex> лежит в отрезке <tex>[\operatorname{pre-order} v; \operatorname{pre-order} v + \operatorname{size} v - 1]</tex>.
}}
{{Утверждение
|statement=В качестве <tex>\operatorname{inlabel} v</tex> можно выбрать <tex>\operatorname{pre-order} u</tex>, кратное максимальной степени двойки, где <tex>u \in S(v)</tex>.
|proof=
Пусть <tex>\operatorname{inlabel} v = \operatorname{pre-order} u = k2^b</tex>, <tex>b</tex> {{---}} максимально.Пусть есть вершина <tex>u' \in S(v)</tex> такая, что <tex>\operatorname{pre-order} u' = k'2^b</tex>.
Так как в отрезке, соответствующем вершине <tex>v</tex> есть два числа, кратных <tex>2^b</tex>, то
там есть и число, кратное <tex>2^{b+1}</tex>. Но тогда <tex>\operatorname{inlabel} v</tex> выбран неверно.
Значит, в поддереве <tex>v</tex> есть только одна такая вершина <tex>u</tex>, что <tex>2^{max} | \operatorname{pre-order} u</tex>.
Рассмотрим два случая.
'''Первый случай''' <tex>\operatorname{inlabel} v = \operatorname{pre-order} v</tex>
Других таких вершин <tex>u'</tex>, что <tex>u'</tex> дает такую же степень двойки, нет.
Значит, во всех поддеревьях <tex>v</tex> значения <tex>\operatorname{inlabel}</tex> отличаются
от <tex>\operatorname{inlabel} v</tex>.
'''Второй случай''' <tex>\operatorname{inlabel} v = \operatorname{pre-order} u</tex>, <tex>u \in S(v), u \ne v</tex>. Так как в поддереве <tex>v</tex> представлены все <tex>\operatorname{pre-order}</tex>-ы из отрезка <tex>[\operatorname{pre-order} v; \operatorname{pre-order} v + \operatorname{size} v - 1]</tex>, то рассмотрим того непосредственного потомка <tex>w</tex> вершины <tex>v</tex>, что <tex>u \in S(w)</tex>. Тогда, так как степень двойки у <tex>u</tex> максимальна, по утверждению в начале доказательства, других вершин с такой же степенью двойки нет, то <tex>\operatorname{inlabel} w = \operatorname{inlabel} v = \operatorname{pre-order} u</tex>. Так как отрезки, соответствующие поддеревьям сыновей, не пересекаются, не найдется другого <tex>w'</tex> {{---}} потомок <tex>v</tex>, что в поддереве <tex>w'</tex> есть вершина с такой же степенью двойки. Значит, все вершины <tex>v'</tex>, у которых <tex>\operatorname{inlabel} v' = \operatorname{inlabel} v</tex> находятся в поддереве <tex>w</tex>.
Получили, что прообраз <tex>\operatorname{inlabel} v</tex> в вершине <tex>v</tex> или обрывается, или продолжается вниз ровно в одного потомка. Значит, прообраз <tex>\operatorname{inlabel} v</tex> {{---}} простой путь из какой-то вершины вниз в <tex>T</tex>, что и требовалось доказать.
{{Утверждение
|statement=<tex>\operatorname{inlabel} v = 2^i \lfloor\frac{\operatorname{pre-order} v + \operatorname{size} v}{2^i}\rfloor</tex>, где <tex>i = \lfloor\log_2 ((\operatorname{pre-order} - 1) v \oplus (\operatorname{pre-order} v + \operatorname{size} v - 1)) \rfloor + 1</tex>
|proof=
Посмотрим на <tex>A = (\operatorname{pre-order} v - 1) \oplus (\operatorname{pre-order} v + \operatorname{size} v - 1)</tex>.
Посмотрим на позицию самго значимого единичного бита <tex>l</tex> в <tex>A</tex>.
Так как в <tex>\operatorname{pre-order} v - 1</tex> там еще <tex>0</tex>, а в <tex>\operatorname{pre-order} v + \operatorname{size} v - 1</tex> {{---}} уже единица, то в отрезке <tex>[\operatorname{pre-order} v; \operatorname{pre-order} v + \operatorname{size} v]</tex> есть число, кратное <tex>2^l</tex>.
Докажем, что нет чисел, кратных <tex>2^{l+1}</tex>. Пусть такое число нашлось. Тогда <tex>l</tex>-й бит менялся хотя бы два раза, а значит, менялся
<tex>l+1</tex>-й бит. А значит, самый значащий отличающийся бит в <tex>\operatorname{pre-order} v - 1</tex> и в <tex>\operatorname{pre-order} v + \operatorname{size} v - 1</tex> больше, чем <tex>l</tex>-й.
Заметим, что функция <tex>\lfloor \log_2 a \rfloor + 1</tex> просто выделяет номер самого значашего единичного бита.
