Изменения

'''Алгоритм Шибера-Вишкина''' (англ.''Schieber-Vishkin '') применяется для нахождения [[Сведение задачи LCA к задаче RMQ|наименьшего общего предка]] (англ. ''least common ancestor'') двух вершин в дереве.

<tex>u \in S(v)</tex> {{---}} вершина <tex>u</tex> находится в поддереве поддерево вершины <tex>v</tex>. Здесь и далее считаем, что вершина является и своим предком, и своим потомком.<br>

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

<tex>\operatorname{pre-orderpreOrder} u \in [\operatorname{pre-orderpreOrder} v; \operatorname{pre-orderpreOrder}v + \operatorname{size} v - 1]</tex>

По определению <tex>\operatorname{pre-orderpreOrder}</tex>, : <tex>\operatorname{pre-orderpreOrder} u</tex> вершин из поддерева <tex>v</tex> образуют

<tex>\operatorname{pre-orderpreOrder}v + 1</tex>, то <tex>\operatorname{pre-orderpreOrder} u</tex> лежит в отрезке <tex>[\operatorname{pre-orderpreOrder} v; \operatorname{pre-orderpreOrder} v + \operatorname{size} v - 1]</tex>.

|statement=В качестве <tex>\operatorname{inlabel} v</tex> можно выбрать <tex>\operatorname{pre-orderpreOrder} u</tex>, кратное максимальной степени двойки, где <tex>u \in S(v)</tex>.

Пусть <tex>\operatorname{inlabel} v = \operatorname{pre-orderpreOrder} u = k2^b</tex>, <tex>b</tex> {{---}} максимально.Пусть есть вершина <tex>u' \in S(v)</tex> такая, что <tex>\operatorname{pre-orderpreOrder} u' = k'2^b</tex>.

Значит, в поддереве <tex>v</tex> есть только одна такая вершина <tex>u</tex>, что <tex>2^{max} | \operatorname{pre-orderpreOrder} u</tex>.

'''Первый случай''' : <tex>\operatorname{inlabel} v = \operatorname{pre-orderpreOrder} v</tex>.&nbsp; Других таких вершин <tex>u'</tex>, что <tex>u'</tex> дает такую же степень двойки, нет.

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

|statement=<tex>\operatorname{inlabel} v = 2^i \bigg\lfloor\dfrac{\operatorname{pre-orderpreOrder} v + \operatorname{size} v}{2^i}\bigg\rfloor</tex>, где <tex>i = \lfloor\log_2 ((\operatorname{pre-orderpreOrder} - 1) v \oplus (\operatorname{pre-orderpreOrder} v + \operatorname{size} v - 1)) \rfloor + 1</tex>

Посмотрим на <tex>A = (\operatorname{pre-orderpreOrder} v - 1) \oplus (\operatorname{pre-orderpreOrder} v + \operatorname{size} v - 1)</tex>. Посмотрим на позицию самго самого значимого единичного бита <tex>l</tex> в <tex>A</tex>.

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

<tex>l+1</tex>-й бит. А значит, самый значащий отличающийся бит в <tex>\operatorname{pre-orderpreOrder} v - 1</tex> и в <tex>\operatorname{pre-orderpreOrder} v + \operatorname{size} v - 1</tex> больше, чем <tex>l</tex>-й.

Посчитаем для каждого <tex>\operatorname{inlabel} v</tex> множество всех его потомков предков в <tex>B</tex> по основным ребрам. Заметим, что для хранения одного потомка предка достаточно хранить только его высоту в дереве. Чтобы восстановить его значение, нужно просто подняться на <tex>\Delta h</tex> вверх от вершины <tex>v</tex>. Поэтому, все это множество можно уместить в целое число: <tex>i</tex>-й бит будет единицей, если есть потомок предок на высоте <tex>i</tex>. Назовем это число, отвечающее множеству предков, <tex>\operatorname{ascendant} v</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 leqslant \operatorname{level} y</tex>, и <tex>y</tex>, в противном случае. Теперь рассмотрим случай, когда <tex>\operatorname{inlabel} x \ne \operatorname{inlabel} y</tex>, то есть <tex>x</tex> и <tex>y</tex> принадлежат разным простым путям.

#<tex>i \leftarrow = \lfloor\log_2 (\operatorname{inlabel} x \oplus \operatorname{inlabel} y)\rfloor</tex>#<tex>path \leftarrow = 2^i \lfloor\dfrac{(\operatorname{ascendant} x) \wedge (\operatorname{ascendant} y)}{2^i}\rfloor</tex>#<tex>\operatorname{inlabel} LCA(x, y) \leftarrow = \lfloor\dfrac12(path \oplus (path - 1))\rfloor + 1</tex>

Подсчет каждого из массивов <tex> \operatorname{inlabel} </tex> и <tex> \operatorname{preOrder}</tex> занимает <tex>O(n)</tex>. Это : <tex> \operatorname{preOrder}</tex> можно сделатьпосчитать, например, [[Обход в глубину, цвета вершин|обходом в глубину]], а <tex> \operatorname{inlabel} </tex> выражается через <tex> \operatorname{preOrder}</tex>, как описано выше.

Здесь <tex>\operatorname{inlabel} LCA(x, y)</tex> и <tex>\operatorname{head} v'</tex> вычисляются за <tex>O(1)</tex>, следовательно, нужно сделать <tex>O(1)</tex> действий для ответа на запрос.

* [http://ia600208.us.archive.org/12/items/onfindinglowe00schi/onfindinglowe00schi.pdf Оригинальная статьяBaruch Schieber, Uzi Vishkin, "On Finding Lowest Common Ancestors: Simplification and Parallelization"]