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

Алгоритм Шибера-Вишкина применяется для нахождения наименьшего общего предка двух вершин в дереве. Он использует [math]O(n)[/math] времени на подготовку и затем отвечает на каждый запрос за [math]O(1)[/math].

Идея алгоритма

Основная идея алгоритма следующая.

1. Если бы дерево, в котором нужно искать [math]LCA[/math] было бы цепочкой, можно было бы найти [math]LCA(u, v)[/math] просто взяв ту вершину, которая находится в дереве выше.
2. Если дерево — полное двоичное дерево высоты [math]h[/math], то можно сопоставить каждой вершине битовый вектор длиной [math]h[/math] (целое число от [math]0[/math] до [math]2^h-1[/math]) и с помощью битовых операций над этими векторами найти [math]LCA(u, v)[/math]

Тогда, представив данное дерево как полное двоичное дерево, в каждой вершине которого находится цепочка, можно научиться искать [math]LCA(v, u)[/math] в нем за [math]O(1)[/math].

Подготовка

Перенумеруем вершины в порядке префиксного обхода дерева: сначала обходится текущая вершина, затем — поддеревья. Пусть [math]\operatorname{order} : V \to \mathbb{N}[/math] — такой порядок обхода.

Обозначим за [math]\operatorname{size} v[/math] количество вершин в поддереве вершины [math]v[/math]. Здесь и далее считаем, что вершина является и своим предком, и своим потомком.

Утверждение:

Пусть [math]u[/math] — вершина из поддерева [math]v[/math]. Тогда [math]\operatorname{order} u \in [\operatorname{order} v; \operatorname{order}v + \operatorname{size} v - 1][/math]

[math]\triangleright[/math]

По определению [math]\operatorname{order}[/math], [math]\operatorname{order} u[/math] вершин из поддерева [math]v[/math] образуют отрезок натуральных чисел длиной [math]\operatorname{size} v - 1[/math]. Так как этот отрезок начинается с [math]\operatorname{order}v + 1[/math], то [math]\operatorname{order} u[/math] — отрезок [math][\operatorname{order} v; \operatorname{order} v + \operatorname{size} v - 1][/math].

[math]\triangleleft[/math]

Покроем дерево путями. А именно, сопоставим каждой вершине [math]v[/math] число [math]\operatorname{chain} v[/math] такое, что прообраз каждого [math]\operatorname{chain} v[/math] в [math]T[/math] связен и является простым путем от какой-то вершины вниз до листа.

Утверждение:

В качестве [math]\operatorname{chain} v[/math] можно выбрать [math]\operatorname{order} u[/math], кратное максимальной степени двойки, где [math]u \in S(v)[/math].

[math]\triangleright[/math]

?

[math]\triangleleft[/math]

Обработка запроса

Пусть [math]x[/math], [math]y[/math] — вершины в исходном дереве [math]LCA[/math] которых необходимо найти. Если [math]\operatorname{inlabel} x = \operatorname{inlabel} y[/math], то они принадлежат одному простому пути, а следовательно ответом на запрос является [math]x[/math], если [math]\operatorname{inlabel} x \le \operatorname{inlabel} y[/math], и [math]y[/math], в противном случае. Теперь рассмотрим случай, когда [math]\operatorname{inlabel} x \ne \operatorname{inlabel} y[/math], то есть [math]x[/math] и [math]y[/math] принадлежат разным простым путям.