Изменения
Нет описания правки
Основная идея алгоритма следующая.
# Если бы дерево, в котором нужно искать <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{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>\operatorname{inlabel} v</tex> в вершине <tex>v</tex> или обрывается, или продолжается вниз ровно в одного потомка. Значит, прообраз <tex>\operatorname{inlabel} v</tex> {{---}} цепочка простой путь из какой-то вершины вниз в <tex>T</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>\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>\operatorname{level} v</tex> {{---}} глубина вершины <tex>v</tex> в <tex>T</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>.
Сначала найдем <tex>LCA(\operatorname{inlabel} x, \operatorname{inlabel} y)</tex> по каркасным ребрам. Для этого вомпользуемся посчитанными значениями <tex>\operatorname{ascendant} v</tex>.
{{Утверждение
|statement= Следующие вычисления позволяют найти <tex>LCA(\operatorname{inlabel} x, \operatorname{inlabel} y) = 2^i((2(\frac x{2^{i+1}})) \,|\, 1)</tex>, где : #<tex>i = \logleftarrow \lfloor\log_2 (\operatorname{inlabel} x \oplus \operatorname{inlabel} y)\rfloor</tex>|proof= Пусть #<tex>path \leftarrow 2^i</tex> \frac{(\operatorname{ascendant} x) \wedge (\operatorname{---ascendant}y)}{2^i} индекс самой правой единицы в двоичном представлении <tex>b</tex>. Из того, что <tex>b</tex> общий предок #<tex>LCA(\operatorname{inlabel} x</tex> и <tex>, \operatorname{inlabel} y</tex> в полном двоичном дереве следует, что <tex>l) \leftarrow \frac12(path \oplus (path -i1)) + 1</tex> левых бит, совпадающих в |proof=<tex>\operatorname{inlabel} x</tex> и <tex>\operatorname{inlabel} y</tex>, должны быть такими же и {{---}} вершины в <tex>bB</tex>. Биты в их записи задают задают их местоположение в дереве.Ноль {{---}} спуститься влево, единица {{---}} спуститься вправо или остаться здесь. Значит, а так как наиболее значимый бит побитового исключающего или их номеров даст глубину, на которой пути до этих вершин начинают расходиться. Это и хранится в <tex>bi</tex> наименьший общий предок. Значит, то мы нашли <tex>iLCA</tex> {{---}} минимальный такой индекспо каркасным ребрам. То есть Однако, могло случиться так, что <tex>iLCA</tex> самый левый битпо основным ребрам, поиском которого мы занимаемся, находится выше (он не может находиться ниже или в котором различаются стороне, так как все основные ребра направлены вниз). Взяв побитовое и <tex>\operatorname{inlabelascendant} x</tex> и <tex>\operatorname{inlabelascendant} y</tex>, в старших единичных битах мы получим путь от корня по основным ребрам до этих вершин. А двоичное представление При этом, про те биты, которые отвечают за уровни ниже <tex>bLCA</tex> состоит из , ничего не известно. Поэтому, нужно их обнулить. Умножение и деление на <tex>l-2^i</tex> левых бит обнулят ненужные биты. После этого, для нахождения <tex>\operatorname{inlabel} xLCA</tex> (или по основным ребрам, нужно найти в <tex>\operatorname{inlabel} ypath</tex>), единички и наименее значимый единичный бит. Формула <tex>i\frac12(x \oplus (x - 1)) + 1</tex> нулейимеено это и делает.
}}
===Запрос===
Здесь нужно сделать <tex>O(1)</tex> действий для ответа на запрос.
==Ссылки==
[http://ia600208.us.archive.org/12/items/onfindinglowe00schi/onfindinglowe00schi.pdf Оригинальная статья]
