Алгоритм Шибера-Вишкина

2012-06-22T06:54:52Z

178.178.26.214: /* Построение */

''Алгоритм Шибера-Вишкина'' применяется для нахождения наименьшего общего предка двух вершин в дереве.
Он использует <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{inlabel} v</tex> такое, что прообраз каждого <tex>\operatorname{inlabel} v</tex> в <tex>T</tex> связен и является простым путем от какой-то вершины вниз до листа.

{{Утверждение
|statement=В качестве <tex>\operatorname{inlabel} v</tex> можно выбрать <tex>\operatorname{order} u</tex>, кратное максимальной степени двойки, где <tex>u \in S(v)</tex>.
|proof=
Пусть <tex>\operatorname{inlabel} v = \operatorname{order} u = k2^b</tex>, <tex>b</tex> {{---}} максимально.
Пусть есть вершина <tex>u' \in S(i)</tex> такая, что <tex>\operatorname{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>\operatorname{order} u \hdots 2^{max}</tex>.

Рассмотрим два случая.

'''Первый случай''' <tex>\operatorname{inlabel} v = \operatorname{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{order} u</tex>, <tex>u \in S(v), u \ne v</tex>
Так как в поддереве <tex>v</tex> представлены все <tex>\operatorname{order}</tex>-ы из отрезка <tex>[\operatorname{order} v; \operatorname{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{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>w</tex>, получим требуемое.
}}

{{Утверждение
|statement=<tex>\operatorname{inlabel} v = 2^i (\frac{\operatorname{order} v + \operatorname{size} v}{2^i})</tex>, где <tex>i = \lfloor\log_2 (\operatorname{order} v \oplus (\operatorname{order} v + \operatorname{size} v)) \rfloor + 1</tex>
|proof=
Посмотрим на <tex>A = \operatorname{order} v \oplus (\operatorname{order} v + \operatorname{size} v)</tex>.
Посмотрим на позицию самой правой единицы <tex>l</tex> в <tex>A</tex>.

Так как в <tex>\operatorname{order} v</tex> там еще <tex>0</tex>, а в <tex>\operatorname{order} v + \operatorname{size} v</tex> {{---}} уже единица, то в отрезке <tex>[\operatorname{order} v; \operatorname{order} v + \operatorname{size} v]</tex> есть число, кратное <tex>2^l</tex>.

Докажем, что нет чисел, кратных <tex>2^{l+1}</tex>. Пусть такое число нашлось. Тогда <tex>l</tex>-й бит менялся хотя бы два раза, а значит, менялся
<tex>l+1</tex>-й бит. А значит, самый значащий отличающийся бит в <tex>\operatorname{order} v</tex> и в <tex>\operatorname{order} v + \operatorname{size} v</tex> больше, чем <tex>l</tex>-й.

Заметим, что функция <tex>\lfloor \log_2 a \rfloor + 1</tex> просто выделяет номер самого значашего единичного бита.

Функция <tex>2^l\frac{a}{2^l}</tex> обнуляет все биты младше <tex>l</tex>-го.

Чтобы получить из отрезка число, кратное <tex>2^l</tex>, будучи уверенными, что оно там есть, достаточно обнулить <tex>l</tex> битов в правой границе отрезка.
}}

Каждое значение <tex>\operatorname{inlabel} v</tex> соответствует вершине в полном двоичном дереве высоты <tex>h=\lceil\log_2 n\rceil</tex>. В двоичном дереве будем нумеровать вершины в инфиксном порядке: обойдем левое поддерево, занумеруем вершину, обойдем правое поддерево. В двоичном дереве будет ребро между вершинами <tex>\operatorname{inlabel} v</tex> и <tex>\operatorname{inlabel} u</tex>, если в начальном дереве есть ребро <tex>v\to u</tex>. Стандартных для двоичного дерева
ребер не будет. Они нужны только для того, чтобы занумеровать вершины и для следующего утверждения.

{{Утверждение
|statement=Если в начальном дереве есть ребро <tex>v\to u</tex> (<tex>u \in S(v)</tex>), то в построенном двоичном дереве
<tex>\operatorname{inorder} u \in S(\operatorname{inorder} v)</tex>
|proof=
}}

Посчитаем для каждого <tex>\operatorname{inlabel} v</tex> множество всех его потомков в двоичном дереве. Заметим, что
для хранения одного потомка достаточно хранить только его высоту в дереве. Чтобы восстановить его значение, нужно
просто подняться на <tex>\Delta h</tex> вверх от вершины <tex>v</tex>. Поэтому, все это множество можно уместить в
число: <tex>i</tex>-й бит будет единицей, если есть потомок на высоте <tex>i</tex>. Назовем это число <tex>\operatorname{ascendant} v</tex>.

В дальнейшем <tex>\operatorname{ascendant} v </tex> поможет в поиске <tex>LCA(\operatorname{inlabel} v, \operatorname{inlabel} u</tex>. Также, нам понадобится еще следующая информация. <tex>\operatorname{head} v</tex> {{---}} самая не глубокая вершина <tex>u</tex> такая, что <tex>\operatorname{inlabel} v = \operatorname{inlabel} u</tex>.

==Обработка запроса==
Пусть <tex>x</tex>, <tex>y</tex> {{---}} вершины в исходном дереве <tex>LCA</tex> которых необходимо найти. Если <tex>\operatorname{inlabel} x = \operatorname{inlabel} y</tex>, то они принадлежат одному простому пути, а следовательно ответом на запрос является <tex>x</tex>, если <tex>\operatorname{level} x \le \operatorname{level} y</tex>, и <tex>y</tex>, в противном случае. Теперь рассмотрим случай, когда <tex>\operatorname{inlabel} x \ne \operatorname{inlabel} y</tex>, то есть <tex>x</tex> и <tex>y</tex> принадлежат разным простым путям. Найдем <tex>b = LCA(\operatorname{inlabel} x, \operatorname{inlabel} y)</tex>.

{{Утверждение
|statement= <tex>LCA(\operatorname{inlabel} x, \operatorname{inlabel} y) = 2^i((2(\frac x{2^{i+1}})) \,|\, 1)</tex>, где <tex>i = \log(\operatorname{inlabel} x \oplus \operatorname{inlabel} y)</tex>
|proof= Пусть <tex>i</tex> {{---}} индекс самой правой единицы в двоичном представлении <tex>b</tex>. Из того, что <tex>b</tex> общий предок <tex>\operatorname{inlabel} x</tex> и <tex>\operatorname{inlabel} y</tex> в полном двоичном дереве следует, что <tex>l-i</tex> левых бит, совпадающих в <tex>\operatorname{inlabel} x</tex> и <tex>\operatorname{inlabel} y</tex>, должны быть такими же и в <tex>b</tex>, а так как <tex>b</tex> наименьший общий предок, то <tex>i</tex> {{---}} минимальный такой индекс. То есть <tex>i</tex> самый левый бит, в котором различаются <tex>\operatorname{inlabel} x</tex> и <tex>\operatorname{inlabel} y</tex>. А двоичное представление <tex>b</tex> состоит из <tex>l-i</tex> левых бит <tex>\operatorname{inlabel} x</tex> (или <tex>\operatorname{inlabel} y</tex>), единички и <tex>i</tex> нулей.
}}

Найдем вершину <tex>\operatorname{inorder} z</tex>, где <tex>z = LCA(x, y)</tex>. На прошлом шаге была найдена вершина
<tex>LCA(\operatorname{inlabel} x, \operatorname{inlabel} y)</tex>. Если бы в двоичном дереве были представлены все вершины,
то это и было бы ответом. Но такой вершины может не оказаться. Воспользуемся значениями <tex>\operatorname{ascendant} \operatorname{inlabel} x</tex> и <tex>\operatorname{ascendant} \operatorname{inlabel} y</tex>. Они характеризуют пути
из вершин <tex>\operatorname{inlabel} x</tex> и <tex>\operatorname{inlabel} x</tex> к корню. С их помощью (с помощью
операции ''логическое и''), можно получить список вершин, через которые проходят оба эти пути и взять с пересечения
самую низкую посещаемую обоими.

Для этого можно воспользоваться описанным при построении методом для нахождения <tex>\operatorname{inlabel} v</tex>.
После этих действий нами был получен путь, в котором находится ответ. Осталось посмотреть на точки входа
<tex>x</tex> и <tex>y</tex> на путь <tex>\operatorname{inlabel} LCA(x, y)</tex>.
Это можно сделать с помощью посчитанной функции <tex>\operatorname{head}</tex>: найти <tex>\operatorname{head} v'</tex>, где <tex>v'</tex> {{---}} вершина предпоследнего пути в пути. Тогда, поднявшись от нее на один вверх по начальному дереву,
получим искомую точку входа.

Имея две точки входа, можно, как и в первом случае, сравнить их по высоте и выбрать более высокое из них.

==Оценка сложности==
===Построение===
Подсчет каждого из массивов занимает <tex>O(n)</tex>. Это можно сделать, например, обходом в глубину.

===Запрос===
Здесь нужно сделать <tex>O(1)</tex> действий для ответа на запрос.

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

Алгоритм Шибера-Вишкина