1632
правки
Изменения
м
Здесь <tex>\operatorname{inlabel} LCA(x, y)</tex> и <tex>\operatorname{head} v'</tex> вычисляются за <tex>O(1)</tex>, следовательно, нужно сделать <tex>O(1)</tex> действий для ответа на запрос.
rollbackEdits.php mass rollback
<tex>T</tex> {{---}} входное дерево с <tex>n</tex> вершинами. Для него нужно отвечать на запросы <tex>LCA</tex>.<br>
<tex>B</tex> {{---}} полное [[Дерево поиска, наивная реализация|двоичное дерево]] с не менее, чем <tex>n</tex> вершинами. Будет введено и объяснено дальше.<br>
<tex>u \in S(v)</tex> {{---}} вершина <tex>u</tex> находится в поддереве поддерево вершины <tex>v</tex>. Здесь и далее считаем, что вершина является и своим предком, и своим потомком.<br>
<tex>v</tex> ''выше'' <tex>u</tex> {{---}} то же самое, что <tex>u \in S(v)</tex>. Корень выше любой вершины.
Перенумеруем вершины в порядке [[Дерево поиска, наивная реализация|префиксного обхода дерева: сначала обрабатывается текущая вершина, затем {{---}} поддеревья.Пусть <tex>\operatorname{preOrder} : V \to \mathbb{N}</tex> {{---}} такой порядок обхода]]. Обозначим за <tex>\operatorname{size} v</tex> количество вершин в поддереве вершины <tex>v</tex>.
{{Утверждение
{{Утверждение
|statement=<tex>\operatorname{inlabel} v = 2^i \bigg\lfloor \dfrac{\operatorname{preOrder} v + \operatorname{size} v}{2^i}\bigg\rfloor</tex>, где <tex>i = \lfloor\log_2 ((\operatorname{preOrder} - 1) v \oplus (\operatorname{preOrder} v + \operatorname{size} v - 1)) \rfloor + 1</tex>
|proof=
Посмотрим на <tex>A = (\operatorname{preOrder} v - 1) \oplus (\operatorname{preOrder} v + \operatorname{size} v - 1)</tex>.
Посмотрим на позицию самго самого значимого единичного бита <tex>l</tex> в <tex>A</tex>.
Так как в <tex>\operatorname{preOrder} v - 1</tex> там еще <tex>0</tex>, а в <tex>\operatorname{preOrder} v + \operatorname{size} v - 1</tex> {{---}} уже единица, то в отрезке <tex>[\operatorname{preOrder} v; \operatorname{preOrder} v + \operatorname{size} v]</tex> есть число, кратное <tex>2^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>\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>.
|statement=Следующие вычисления позволяют найти <tex>\operatorname{inlabel} LCA(x,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>
|proof=<tex>\operatorname{inlabel} x</tex> и <tex>\operatorname{inlabel} y</tex> {{---}} вершины в <tex>B</tex>. Биты в их записи задают задают их местоположение в дереве.
Ноль {{---}} спуститься влево, единица {{---}} спуститься вправо или остаться здесь. Значит, наиболее значимый бит побитового исключающего или их номеров даст глубину, на которой пути до этих вершин начинают расходиться. Это и хранится в <tex>i</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>, как описано выше.
===Запрос===
== См.также ==
*[[Метод двоичного подъема]]
== Источники информации ==
* [http://ia600208.us.archive.org/12/items/onfindinglowe00schi/onfindinglowe00schi.pdf Baruch Schieber, Uzi Vishkin. , "On Finding Lowest Common Ancestors: Simplification and Parallelization"]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Задача о наименьшем общем предке]]
