Алгоритм Шибера-Вишкина — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 20 промежуточных версий 3 участников)
Строка 15: Строка 15:
 
<tex>T</tex> {{---}} входное дерево с <tex>n</tex> вершинами. Для него нужно отвечать на запросы <tex>LCA</tex>.<br>
 
<tex>T</tex> {{---}} входное дерево с <tex>n</tex> вершинами. Для него нужно отвечать на запросы <tex>LCA</tex>.<br>
 
<tex>B</tex> {{---}} полное [[Дерево поиска, наивная реализация|двоичное дерево]]  с не менее, чем <tex>n</tex> вершинами. Будет введено и объяснено дальше.<br>
 
<tex>B</tex> {{---}} полное [[Дерево поиска, наивная реализация|двоичное дерево]]  с не менее, чем <tex>n</tex> вершинами. Будет введено и объяснено дальше.<br>
<tex>u \in S(v)</tex> {{---}} вершина <tex>u</tex> находится в поддереве вершины <tex>v</tex>. Здесь и далее считаем, что вершина является и своим предком, и своим потомком.<br>
+
<tex>S(v)</tex> {{---}} поддерево вершины <tex>v</tex>. Здесь и далее считаем, что вершина является и своим предком, и своим потомком.<br>
 
<tex>v</tex> ''выше'' <tex>u</tex> {{---}} то же самое, что <tex>u \in S(v)</tex>. Корень выше любой вершины.
 
<tex>v</tex> ''выше'' <tex>u</tex> {{---}} то же самое, что <tex>u \in S(v)</tex>. Корень выше любой вершины.
  
 
+
Перенумеруем вершины в порядке [[Дерево поиска, наивная реализация|префиксного обхода дерева]]. Обозначим за <tex>\operatorname{size} v</tex> количество вершин в поддереве вершины <tex>v</tex>.  
Перенумеруем вершины в порядке префиксного обхода дерева: сначала обрабатывается текущая вершина, затем {{---}} поддеревья.
 
Пусть <tex>\operatorname{pre-order} : V \to \mathbb{N}</tex> {{---}} такой порядок обхода.
 
 
 
Обозначим за <tex>\operatorname{size} v</tex> количество вершин в поддереве вершины <tex>v</tex>.  
 
  
 
{{Утверждение
 
{{Утверждение
 
|statement=Пусть <tex>u \in S(v)</tex>. Тогда  
 
|statement=Пусть <tex>u \in S(v)</tex>. Тогда  
<tex>\operatorname{pre-order} u \in [\operatorname{pre-order} v; \operatorname{pre-order}v + \operatorname{size} v - 1]</tex>
+
<tex>\operatorname{preOrder} u \in [\operatorname{preOrder} v; \operatorname{preOrder}v + \operatorname{size} v - 1]</tex>
 
|proof=
 
|proof=
По определению <tex>\operatorname{pre-order}</tex>, <tex>\operatorname{pre-order} u</tex> вершин из поддерева <tex>v</tex> образуют  
+
По определению <tex>\operatorname{preOrder}</tex>: <tex>\operatorname{preOrder} u</tex> вершин из поддерева <tex>v</tex> образуют  
 
отрезок натуральных чисел длиной <tex>\operatorname{size} v - 1</tex>. Так как этот отрезок начинается с  
 
отрезок натуральных чисел длиной <tex>\operatorname{size} v - 1</tex>. Так как этот отрезок начинается с  
<tex>\operatorname{pre-order}v + 1</tex>, то <tex>\operatorname{pre-order} u</tex> лежит в отрезке <tex>[\operatorname{pre-order} v; \operatorname{pre-order} v + \operatorname{size} v - 1]</tex>.
+
<tex>\operatorname{preOrder}v + 1</tex>, то <tex>\operatorname{preOrder} u</tex> лежит в отрезке <tex>[\operatorname{preOrder} v; \operatorname{preOrder} v + \operatorname{size} v - 1]</tex>.
 
}}
 
}}
  
Строка 36: Строка 32:
  
 
{{Утверждение
 
{{Утверждение
|statement=В качестве <tex>\operatorname{inlabel} v</tex> можно выбрать <tex>\operatorname{pre-order} u</tex>, кратное максимальной степени двойки, где <tex>u \in S(v)</tex>.
+
|statement=В качестве <tex>\operatorname{inlabel} v</tex> можно выбрать <tex>\operatorname{preOrder} u</tex>, кратное максимальной степени двойки, где <tex>u \in S(v)</tex>.
 
|proof=
 
|proof=
Пусть <tex>\operatorname{inlabel} v = \operatorname{pre-order} u = k2^b</tex>, <tex>b</tex> {{---}} максимально.
+
Пусть <tex>\operatorname{inlabel} v = \operatorname{preOrder} u = k2^b</tex>, <tex>b</tex> {{---}} максимально.
Пусть есть вершина <tex>u' \in S(v)</tex> такая, что <tex>\operatorname{pre-order} u' = k'2^b</tex>.
+
Пусть есть вершина <tex>u' \in S(v)</tex> такая, что <tex>\operatorname{preOrder} u' = k'2^b</tex>.
 
Так как в отрезке, соответствующем вершине <tex>v</tex> есть два числа, кратных <tex>2^b</tex>, то
 
Так как в отрезке, соответствующем вершине <tex>v</tex> есть два числа, кратных <tex>2^b</tex>, то
 
там есть и число, кратное <tex>2^{b+1}</tex>. Но тогда <tex>\operatorname{inlabel} v</tex> выбран неверно.
 
там есть и число, кратное <tex>2^{b+1}</tex>. Но тогда <tex>\operatorname{inlabel} v</tex> выбран неверно.
Значит, в поддереве <tex>v</tex> есть только одна такая вершина <tex>u</tex>, что <tex>2^{max} | \operatorname{pre-order} u</tex>.
+
Значит, в поддереве <tex>v</tex> есть только одна такая вершина <tex>u</tex>, что <tex>2^{max} | \operatorname{preOrder} u</tex>.
  
 
Рассмотрим два случая.  
 
Рассмотрим два случая.  
  
'''Первый случай''' <tex>\operatorname{inlabel} v = \operatorname{pre-order} v</tex>
+
'''Первый случай''': <tex>\operatorname{inlabel} v = \operatorname{preOrder} v</tex>.&nbsp; Других таких вершин <tex>u'</tex>, что <tex>u'</tex> дает такую же степень двойки, нет.
Других таких вершин <tex>u'</tex>, что <tex>u'</tex> дает такую же степень двойки, нет.
 
 
Значит, во всех поддеревьях <tex>v</tex> значения <tex>\operatorname{inlabel}</tex> отличаются
 
Значит, во всех поддеревьях <tex>v</tex> значения <tex>\operatorname{inlabel}</tex> отличаются
 
от <tex>\operatorname{inlabel} v</tex>.
 
от <tex>\operatorname{inlabel} v</tex>.
  
'''Второй случай''' <tex>\operatorname{inlabel} v = \operatorname{pre-order} u</tex>, <tex>u \in S(v), u \ne v</tex>. Так как в поддереве <tex>v</tex> представлены все <tex>\operatorname{pre-order}</tex>-ы из отрезка <tex>[\operatorname{pre-order} v; \operatorname{pre-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{pre-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 = \operatorname{preOrder} u</tex>, <tex>u \in S(v), u \ne v</tex>. Так как в поддереве <tex>v</tex> представлены все <tex>\operatorname{preOrder}</tex>-ы из отрезка <tex>[\operatorname{preOrder} v; \operatorname{preOrder} 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{preOrder} 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>v</tex> или обрывается, или продолжается вниз ровно в одного потомка. Значит, прообраз <tex>\operatorname{inlabel} v</tex> {{---}} простой путь из какой-то вершины вниз в <tex>T</tex>, что и требовалось доказать.
Строка 57: Строка 52:
  
 
{{Утверждение
 
{{Утверждение
|statement=<tex>\operatorname{inlabel} v = 2^i \lfloor\dfrac{\operatorname{pre-order} v + \operatorname{size} v}{2^i}\rfloor</tex>, где <tex>i = \lfloor\log_2 ((\operatorname{pre-order} - 1) v \oplus (\operatorname{pre-order} v + \operatorname{size} v - 1)) \rfloor + 1</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) \oplus (\operatorname{preOrder} v + \operatorname{size} v - 1)) \rfloor</tex>
 
|proof=
 
|proof=
Посмотрим на <tex>A = (\operatorname{pre-order} v - 1) \oplus (\operatorname{pre-order} v + \operatorname{size} v - 1)</tex>.  
+
Посмотрим на <tex>A = (\operatorname{preOrder} v - 1) \oplus (\operatorname{preOrder} v + \operatorname{size} v - 1)</tex>.  
Посмотрим на позицию самго значимого единичного бита <tex>l</tex> в <tex>A</tex>.  
+
Посмотрим на позицию самого значимого единичного бита <tex>l</tex> в <tex>A</tex>.  
  
Так как в <tex>\operatorname{pre-order} v - 1</tex> там еще <tex>0</tex>, а в <tex>\operatorname{pre-order} v + \operatorname{size} v - 1</tex> {{---}} уже единица, то в отрезке <tex>[\operatorname{pre-order} v; \operatorname{pre-order} v + \operatorname{size} v]</tex> есть число, кратное <tex>2^l</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>2^{l+1}</tex>. Пусть такое число нашлось. Тогда <tex>l</tex>-й бит менялся хотя бы два раза, а значит, менялся  
 
Докажем, что нет чисел, кратных <tex>2^{l+1}</tex>. Пусть такое число нашлось. Тогда <tex>l</tex>-й бит менялся хотя бы два раза, а значит, менялся  
<tex>l+1</tex>-й бит. А значит, самый значащий отличающийся бит в <tex>\operatorname{pre-order} v - 1</tex> и в <tex>\operatorname{pre-order} v + \operatorname{size} v - 1</tex> больше, чем <tex>l</tex>-й.
+
<tex>l+1</tex>-й бит. А значит, самый значащий отличающийся бит в <tex>\operatorname{preOrder} v - 1</tex> и в <tex>\operatorname{preOrder} v + \operatorname{size} v - 1</tex> больше, чем <tex>l</tex>-й.
  
 
Заметим, что функция <tex>\lfloor \log_2 a \rfloor + 1</tex> просто выделяет номер самого значашего единичного бита.
 
Заметим, что функция <tex>\lfloor \log_2 a \rfloor + 1</tex> просто выделяет номер самого значашего единичного бита.
Строка 82: Строка 77:
 
}}
 
}}
  
Посчитаем для каждого <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{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>\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>x</tex>, <tex>y</tex> {{---}} вершины в исходном дереве <tex>LCA</tex> которых необходимо найти. Если <tex>\operatorname{inlabel} x = \operatorname{inlabel} y</tex>, то они принадлежат одному простому пути, а следовательно ответом на запрос является <tex>x</tex>, если <tex>\operatorname{level} x \leqslant \operatorname{level} y</tex>, и <tex>y</tex>, в противном случае. Теперь рассмотрим случай, когда <tex>\operatorname{inlabel} x \ne \operatorname{inlabel} y</tex>, то есть <tex>x</tex> и <tex>y</tex> принадлежат разным простым путям.  
  
 
{{Утверждение
 
{{Утверждение
 
|statement=Следующие вычисления позволяют найти <tex>\operatorname{inlabel} LCA(x,y)</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>i = \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>path = 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} LCA(x, y) = \lfloor\dfrac12(path \oplus (path - 1))\rfloor + 1</tex>
 
|proof=<tex>\operatorname{inlabel} x</tex> и <tex>\operatorname{inlabel} y</tex> {{---}} вершины в <tex>B</tex>. Биты в их записи задают задают их местоположение в дереве.
 
|proof=<tex>\operatorname{inlabel} x</tex> и <tex>\operatorname{inlabel} y</tex> {{---}} вершины в <tex>B</tex>. Биты в их записи задают задают их местоположение в дереве.
 
Ноль {{---}} спуститься влево, единица {{---}} спуститься вправо или остаться здесь. Значит, наиболее значимый бит побитового исключающего или их номеров даст глубину, на которой пути до этих вершин начинают расходиться. Это и хранится в <tex>i</tex>.
 
Ноль {{---}} спуститься влево, единица {{---}} спуститься вправо или остаться здесь. Значит, наиболее значимый бит побитового исключающего или их номеров даст глубину, на которой пути до этих вершин начинают расходиться. Это и хранится в <tex>i</tex>.
Строка 111: Строка 106:
 
==Оценка сложности==
 
==Оценка сложности==
 
===Построение===
 
===Построение===
Подсчет каждого из массивов занимает <tex>O(n)</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>O(1)</tex> действий для ответа на запрос.
+
<tex>\operatorname{inlabel} LCA(x, y)</tex> и <tex>\operatorname{head} v'</tex> вычисляются за <tex>O(1)</tex>, следовательно, нужно сделать <tex>O(1)</tex> действий для ответа на запрос.
  
 
== См.также ==
 
== См.также ==
Строка 120: Строка 115:
 
*[[Метод двоичного подъема]]
 
*[[Метод двоичного подъема]]
 
== Источники информации ==
 
== Источники информации ==
[http://ia600208.us.archive.org/12/items/onfindinglowe00schi/onfindinglowe00schi.pdf Оригинальная статья]
+
* [http://ia600208.us.archive.org/12/items/onfindinglowe00schi/onfindinglowe00schi.pdf Baruch Schieber, Uzi Vishkin, "On Finding Lowest Common Ancestors: Simplification and Parallelization"]
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Задача о наименьшем общем предке]]
 
[[Категория: Задача о наименьшем общем предке]]

Текущая версия на 19:07, 4 сентября 2022

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

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

Утверждение:
Пусть [math]u \in S(v)[/math]. Тогда [math]\operatorname{preOrder} u \in [\operatorname{preOrder} v; \operatorname{preOrder}v + \operatorname{size} v - 1][/math]
[math]\triangleright[/math]

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

[math]\operatorname{preOrder}v + 1[/math], то [math]\operatorname{preOrder} u[/math] лежит в отрезке [math][\operatorname{preOrder} v; \operatorname{preOrder} 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{preOrder} u[/math], кратное максимальной степени двойки, где [math]u \in S(v)[/math].
[math]\triangleright[/math]

Пусть [math]\operatorname{inlabel} v = \operatorname{preOrder} u = k2^b[/math], [math]b[/math] — максимально. Пусть есть вершина [math]u' \in S(v)[/math] такая, что [math]\operatorname{preOrder} 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{preOrder} u[/math].

Рассмотрим два случая.

Первый случай: [math]\operatorname{inlabel} v = \operatorname{preOrder} 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{preOrder} u[/math], [math]u \in S(v), u \ne v[/math]. Так как в поддереве [math]v[/math] представлены все [math]\operatorname{preOrder}[/math]-ы из отрезка [math][\operatorname{preOrder} v; \operatorname{preOrder} 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{preOrder} 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 \bigg\lfloor \dfrac{\operatorname{preOrder} v + \operatorname{size} v}{2^i}\bigg\rfloor[/math], где [math]i = \lfloor\log_2 ((\operatorname{preOrder} - 1) \oplus (\operatorname{preOrder} v + \operatorname{size} v - 1)) \rfloor[/math]
[math]\triangleright[/math]

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

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

Докажем, что нет чисел, кратных [math]2^{l+1}[/math]. Пусть такое число нашлось. Тогда [math]l[/math]-й бит менялся хотя бы два раза, а значит, менялся [math]l+1[/math]-й бит. А значит, самый значащий отличающийся бит в [math]\operatorname{preOrder} v - 1[/math] и в [math]\operatorname{preOrder} 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 \leqslant \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]:
  1. [math]i = \lfloor\log_2 (\operatorname{inlabel} x \oplus \operatorname{inlabel} y)\rfloor[/math]
  2. [math]path = 2^i \lfloor\dfrac{(\operatorname{ascendant} x) \wedge (\operatorname{ascendant} y)}{2^i}\rfloor[/math]
  3. [math]\operatorname{inlabel} LCA(x, y) = \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] \operatorname{inlabel} [/math] и [math] \operatorname{preOrder}[/math] занимает [math]O(n)[/math]: [math] \operatorname{preOrder}[/math] можно посчитать, например, обходом в глубину, а [math] \operatorname{inlabel} [/math] выражается через [math] \operatorname{preOrder}[/math], как описано выше.

Запрос

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

См.также

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