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

Алгоритм Шибера-Вишкина (англ.Schieber-Vishkin ) применяется для нахождения наименьшего общего предка (англ. least common ancestor) двух вершин в дереве. Он использует [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]T[/math] — входное дерево с [math]n[/math] вершинами. Для него нужно отвечать на запросы [math]LCA[/math].
[math]B[/math] — полное двоичное дерево с не менее, чем [math]n[/math] вершинами. Будет введено и объяснено дальше.
[math]u \in S(v)[/math] — вершина [math]u[/math] находится в поддереве вершины [math]v[/math]. Здесь и далее считаем, что вершина является и своим предком, и своим потомком.
[math]v[/math] выше [math]u[/math] — то же самое, что [math]u \in S(v)[/math]. Корень выше любой вершины.

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

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

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

Пусть [math]u \in S(v)[/math]. Тогда [math]\operatorname{pre-order} u \in [\operatorname{pre-order} v; \operatorname{pre-order}v + \operatorname{size} v - 1][/math]

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

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

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

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

[math]\triangleright[/math]

Пусть [math]\operatorname{inlabel} v = \operatorname{pre-order} u = k2^b[/math], [math]b[/math] — максимально. Пусть есть вершина [math]u' \in S(v)[/math] такая, что [math]\operatorname{pre-order} u' = k'2^b[/math]. Так как в отрезке, соответствующем вершине [math]v[/math] есть два числа, кратных [math]2^b[/math], то там есть и число, кратное [math]2^{b+1}[/math]. Но тогда [math]\operatorname{inlabel} v[/math] выбран неверно. Значит, в поддереве [math]v[/math] есть только одна такая вершина [math]u[/math], что [math]2^{max} | \operatorname{pre-order} u[/math]. Рассмотрим два случая. Первый случай [math]\operatorname{inlabel} v = \operatorname{pre-order} v[/math] Других таких вершин [math]u'[/math], что [math]u'[/math] дает такую же степень двойки, нет. Значит, во всех поддеревьях [math]v[/math] значения [math]\operatorname{inlabel}[/math] отличаются от [math]\operatorname{inlabel} v[/math]. Второй случай [math]\operatorname{inlabel} v = \operatorname{pre-order} u[/math], [math]u \in S(v), u \ne v[/math]. Так как в поддереве [math]v[/math] представлены все [math]\operatorname{pre-order}[/math]-ы из отрезка [math][\operatorname{pre-order} v; \operatorname{pre-order} v + \operatorname{size} v - 1][/math], то рассмотрим того непосредственного потомка [math]w[/math] вершины [math]v[/math], что [math]u \in S(w)[/math]. Тогда, так как степень двойки у [math]u[/math] максимальна, по утверждению в начале доказательства, других вершин с такой же степенью двойки нет, то [math]\operatorname{inlabel} w = \operatorname{inlabel} v = \operatorname{pre-order} u[/math]. Так как отрезки, соответствующие поддеревьям сыновей, не пересекаются, не найдется другого [math]w'[/math] — потомок [math]v[/math], что в поддереве [math]w'[/math] есть вершина с такой же степенью двойки. Значит, все вершины [math]v'[/math], у которых [math]\operatorname{inlabel} v' = \operatorname{inlabel} v[/math] находятся в поддереве [math]w[/math]. Получили, что прообраз [math]\operatorname{inlabel} v[/math] в вершине [math]v[/math] или обрывается, или продолжается вниз ровно в одного потомка. Значит, прообраз [math]\operatorname{inlabel} v[/math] — простой путь из какой-то вершины вниз в [math]T[/math], что и требовалось доказать.

[math]\triangleleft[/math]

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

[math]\operatorname{inlabel} v = 2^i \lfloor\dfrac{\operatorname{pre-order} v + \operatorname{size} v}{2^i}\rfloor[/math], где [math]i = \lfloor\log_2 ((\operatorname{pre-order} - 1) v \oplus (\operatorname{pre-order} v + \operatorname{size} v - 1)) \rfloor + 1[/math]

[math]\triangleright[/math]

Посмотрим на [math]A = (\operatorname{pre-order} v - 1) \oplus (\operatorname{pre-order} v + \operatorname{size} v - 1)[/math]. Посмотрим на позицию самго значимого единичного бита [math]l[/math] в [math]A[/math]. Так как в [math]\operatorname{pre-order} v - 1[/math] там еще [math]0[/math], а в [math]\operatorname{pre-order} v + \operatorname{size} v - 1[/math] — уже единица, то в отрезке [math][\operatorname{pre-order} v; \operatorname{pre-order} v + \operatorname{size} v][/math] есть число, кратное [math]2^l[/math]. Докажем, что нет чисел, кратных [math]2^{l+1}[/math]. Пусть такое число нашлось. Тогда [math]l[/math]-й бит менялся хотя бы два раза, а значит, менялся [math]l+1[/math]-й бит. А значит, самый значащий отличающийся бит в [math]\operatorname{pre-order} v - 1[/math] и в [math]\operatorname{pre-order} v + \operatorname{size} v - 1[/math] больше, чем [math]l[/math]-й. Заметим, что функция [math]\lfloor \log_2 a \rfloor + 1[/math] просто выделяет номер самого значашего единичного бита. Функция [math]2^l\left\lfloor\dfrac{a}{2^l}\right\rfloor[/math] обнуляет все биты младше [math]l[/math]-го. Чтобы получить из отрезка число, кратное [math]2^l[/math], будучи уверенными, что оно там есть, достаточно обнулить [math]l[/math] битов в правой границе отрезка.

[math]\triangleleft[/math]

Каждое значение [math]\operatorname{inlabel} v[/math] соответствует вершине в полном двоичном дереве [math]B[/math] высоты [math]h=\lceil\log_2 n\rceil[/math]. В дереве на одном наборе вершин будет построено два набора ребер: каркасные и основные. Для каждой вершины [math]v \in V(B)[/math] с уровня, кроме последнего, будут каркасные ребра [math]v\to2v[/math] и [math]v\to2v+1[/math]. Таким образом, вершины в [math]B[/math] будут занумерованы в инфиксном порядке обхода по каркасным ребрам: сначала обрабатывается левое поддерево, потом — вершина, потом — правое поддерево. В [math]B[/math] будет основное ребро между вершинами [math]\operatorname{inlabel} v[/math] и [math]\operatorname{inlabel} u[/math], если в [math]T[/math] есть ребро [math]v\to u[/math]. Корень имеет номер [math]1[/math]. Будем говорить, что вершина [math]u \in B[/math] лежит в поддереве вершины [math]u \in B[/math] ([math]u \in S(v)[/math]), если от [math]v[/math] есть путь до [math]u[/math] по каркасным ребрам.

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

Если в [math]T[/math] есть ребро [math]v\to u[/math], то в [math]B[/math]: [math]\operatorname{inlabel} u \in S(\operatorname{inlabel} v)[/math] Другими словами, все основные ребра направлены вниз.

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

В дальнейшем [math]\operatorname{ascendant} v [/math] поможет в поиске [math]LCA(\operatorname{inlabel} v, \operatorname{inlabel} u)[/math]. Также, нам понадобится еще следующая информация. [math]\operatorname{head} v[/math] — самая не глубокая вершина [math]u[/math] такая, что [math]\operatorname{inlabel} v = \operatorname{inlabel} u[/math]. [math]\operatorname{level} v[/math] — глубина вершины [math]v[/math] в [math]T[/math].

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

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

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

Следующие вычисления позволяют найти [math]\operatorname{inlabel} LCA(x,y)[/math]: [math]i \leftarrow \lfloor\log_2 (\operatorname{inlabel} x \oplus \operatorname{inlabel} y)\rfloor[/math] [math]path \leftarrow 2^i \lfloor\dfrac{(\operatorname{ascendant} x) \wedge (\operatorname{ascendant} y)}{2^i}\rfloor[/math] [math]\operatorname{inlabel} LCA(x, y) \leftarrow \lfloor\dfrac12(path \oplus (path - 1))\rfloor + 1[/math]

[math]\triangleright[/math]

[math]\operatorname{inlabel} x[/math] и [math]\operatorname{inlabel} y[/math] — вершины в [math]B[/math]. Биты в их записи задают задают их местоположение в дереве. Ноль — спуститься влево, единица — спуститься вправо или остаться здесь. Значит, наиболее значимый бит побитового исключающего или их номеров даст глубину, на которой пути до этих вершин начинают расходиться. Это и хранится в [math]i[/math]. Значит, мы нашли [math]LCA[/math] по каркасным ребрам. Однако, могло случиться так, что [math]LCA[/math] по основным ребрам, поиском которого мы занимаемся, находится выше (он не может находиться ниже или в стороне, так как все основные ребра направлены вниз). Взяв побитовое и [math]\operatorname{ascendant} x[/math] и [math]\operatorname{ascendant} y[/math], в старших единичных битах мы получим путь от корня по основным ребрам до этих вершин. При этом, про те биты, которые отвечают за уровни ниже [math]LCA[/math], ничего не известно. Поэтому, нужно их обнулить. Умножение и деление на [math]2^i[/math] обнулят ненужные биты. После этого, для нахождения [math]LCA[/math] по основным ребрам, нужно найти в [math]path[/math] наименее значимый единичный бит. Формула [math]\dfrac12(x \oplus (x - 1)) + 1[/math] имеено это и делает.

[math]\triangleleft[/math]

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

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

Оценка сложности

Построение

Подсчет каждого из массивов занимает [math]O(n)[/math]. Это можно сделать, например, обходом в глубину.

Запрос

Здесь нужно сделать [math]O(1)[/math] действий для ответа на запрос.

См.также

• Алгоритм Тарьяна поиска LCA за O(1) в оффлайн
• Метод двоичного подъема

Источники информации

Оригинальная статья