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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 39 промежуточных версий 6 участников)
Строка 1: Строка 1:
''Алгоритм Шибера-Вишкина'' применяется для нахождения наименьшего общего предка двух вершин в дереве.
+
'''Алгоритм Шибера-Вишкина''' (англ.''Schieber-Vishkin '') применяется для нахождения [[Сведение задачи LCA к задаче RMQ|наименьшего общего предка]] двух вершин в дереве.
Он использует <tex>O(n)</tex> времени на подготовку и затем отвечает на каждый запрос за <tex>O(1)</tex>.
+
Он использует <tex>O(n)</tex> времени на препроцессинг и затем отвечает на каждый запрос за <tex>O(1)</tex>.
  
 
==Идея алгоритма==
 
==Идея алгоритма==
Строка 6: Строка 6:
  
 
# Если бы дерево, в котором нужно искать <tex>LCA</tex> было бы простым путем, можно было бы найти <tex>LCA(u, v)</tex> просто взяв ту вершину, которая находится в дереве ближе к корню.
 
# Если бы дерево, в котором нужно искать <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>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>LCA(v, u)</tex> в нем за <tex>O(1)</tex>.
 
  
==Подготовка==
 
{{Определение
 
|definition=
 
 
<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>v</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{order} : V \to \mathbb{N}</tex> {{---}} такой порядок обхода.
 
  
Обозначим за <tex>\operatorname{size} v</tex> количество вершин в поддереве вершины <tex>v</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{order} u \in [\operatorname{order} v; \operatorname{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{order}</tex>, <tex>\operatorname{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{order}v + 1</tex>, то <tex>\operatorname{order} u</tex> лежит в отрезке <tex>[\operatorname{order} v; \operatorname{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{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{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{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{order} u</tex>.
+
Значит, в поддереве <tex>v</tex> есть только одна такая вершина <tex>u</tex>, что <tex>2^{max} | \operatorname{preOrder} u</tex>.
  
 
Рассмотрим два случая.  
 
Рассмотрим два случая.  
  
'''Первый случай''' <tex>\operatorname{inlabel} v = \operatorname{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{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 = \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\frac{\operatorname{order} v + \operatorname{size} v}{2^i}\rfloor</tex>, где <tex>i = \lfloor\log_2 ((\operatorname{order} - 1) v \oplus (\operatorname{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{order} v - 1) \oplus (\operatorname{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{order} v - 1</tex> там еще <tex>0</tex>, а в <tex>\operatorname{order} v + \operatorname{size} v - 1</tex> {{---}} уже единица, то в отрезке <tex>[\operatorname{order} v; \operatorname{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{order} v - 1</tex> и в <tex>\operatorname{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> просто выделяет номер самого значашего единичного бита.
  
Функция <tex>2^l\frac{a}{2^l}</tex> обнуляет все биты младше <tex>l</tex>-го.  
+
Функция <tex>2^l\left\lfloor\dfrac{a}{2^l}\right\rfloor</tex> обнуляет все биты младше <tex>l</tex>-го.  
  
 
Чтобы получить из отрезка число, кратное <tex>2^l</tex>, будучи уверенными, что оно там есть, достаточно обнулить <tex>l</tex> битов в правой границе отрезка.
 
Чтобы получить из отрезка число, кратное <tex>2^l</tex>, будучи уверенными, что оно там есть, достаточно обнулить <tex>l</tex> битов в правой границе отрезка.
 
}}
 
}}
  
Каждое значение <tex>\operatorname{inlabel} v</tex> соответствует вершине в полном двоичном дереве <tex>B</tex> высоты <tex>h=\lceil\log_2 n\rceil</tex>. В дереве на одном наборе вершин будет построено два набора ребер: ''каркасные'' и ''основные''. Для каждой вершины <tex>v \in V(B)</tex> с уровня, кроме последнего, будут каркасные ребра <tex>v\to2v</tex> и <tex>v\to2v+1</tex>. Таким образом, вершины в <tex>B</tex>  будут занумерованы в инфиксном порядке обхода по каркасным ребрам: обход левого поддерева, нумерация вершины, обход правого поддерева. В <tex>B</tex> будет основное ребро между вершинами <tex>\operatorname{inlabel} v</tex> и <tex>\operatorname{inlabel} u</tex>, если в <tex>T</tex> есть ребро <tex>v\to u</tex>. Корень имеет номер <tex>1</tex>. Будем говорить, что вершина <tex>u \in B</tex> лежит в поддереве вершины <tex>u \in B</tex> (<tex>u \in S(v)</tex>), если от <tex>v</tex> есть путь до <tex>u</tex> по каркасным ребрам.
+
Каждое значение <tex>\operatorname{inlabel} v</tex> соответствует вершине в полном двоичном дереве <tex>B</tex> высоты <tex>h=\lceil\log_2 n\rceil</tex>. В дереве на одном наборе вершин будет построено два набора ребер: ''каркасные'' и ''основные''. Для каждой вершины <tex>v \in V(B)</tex> с уровня, кроме последнего, будут каркасные ребра <tex>v\to2v</tex> и <tex>v\to2v+1</tex>. Таким образом, вершины в <tex>B</tex>  будут занумерованы в инфиксном порядке обхода по каркасным ребрам: сначала обрабатывается левое поддерево, потом {{---}} вершина, потом {{---}} правое поддерево. В <tex>B</tex> будет основное ребро между вершинами <tex>\operatorname{inlabel} v</tex> и <tex>\operatorname{inlabel} u</tex>, если в <tex>T</tex> есть ребро <tex>v\to u</tex>. Корень имеет номер <tex>1</tex>. Будем говорить, что вершина <tex>u \in B</tex> лежит в поддереве вершины <tex>u \in B</tex> (<tex>u \in S(v)</tex>), если от <tex>v</tex> есть путь до <tex>u</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>b = LCA(\operatorname{inlabel} x, \operatorname{inlabel} 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> принадлежат разным простым путям.  
 
 
Сначала найдем <tex>LCA(\operatorname{inlabel} x, \operatorname{inlabel} y)</tex> по каркасным ребрам. Для этого вомпользуемся посчитанными значениями <tex>\operatorname{ascendant} v</tex>.
 
  
 
{{Утверждение
 
{{Утверждение
|statement=Следующие вычисления позволяют найти <tex>LCA(\operatorname{inlabel} x, \operatorname{inlabel} 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\frac{(\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>LCA(\operatorname{inlabel} x, \operatorname{inlabel} y) \leftarrow \lfloor\frac12(path \oplus (path - 1))\rfloor + 1</tex>
+
#<tex>\operatorname{inlabel} LCA(x, y) = \lfloor\dfrac12(path \oplus (path - 1))\rfloor + 1</tex>
|proof=<tex>x</tex> и <tex>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>.
  
 
Значит, мы нашли <tex>LCA</tex> по каркасным ребрам. Однако, могло случиться так, что <tex>LCA</tex> по основным ребрам, поиском которого мы занимаемся, находится выше (он не может находиться ниже или в стороне, так как все основные ребра направлены вниз).  
 
Значит, мы нашли <tex>LCA</tex> по каркасным ребрам. Однако, могло случиться так, что <tex>LCA</tex> по основным ребрам, поиском которого мы занимаемся, находится выше (он не может находиться ниже или в стороне, так как все основные ребра направлены вниз).  
  
Взяв побитовое и <tex>\operatorname{ascendant} x</tex> и <tex>\operatorname{ascendant} y</tex>, в старших единичных битах мы получим путь от корня по основным ребрам до этих вершин. При этом, про те биты, которые отвечают за уровни ниже <tex>LCA</tex>, ничего не известно. Поэтому, нужно их обнулить. Умножение и деление на <tex>2^i</tex> обнулят ненужные биты. После этого, для нахождения <tex>LCA</tex> по основным ребрам, нужно найти в <tex>path</tex> наименее значимый единичный бит. Формула <tex>\frac12(x \oplus (x - 1)) + 1</tex> имеено это и делает.
+
Взяв побитовое и <tex>\operatorname{ascendant} x</tex> и <tex>\operatorname{ascendant} y</tex>, в старших единичных битах мы получим путь от корня по основным ребрам до этих вершин. При этом, про те биты, которые отвечают за уровни ниже <tex>LCA</tex>, ничего не известно. Поэтому, нужно их обнулить. Умножение и деление на <tex>2^i</tex> обнулят ненужные биты. После этого, для нахождения <tex>LCA</tex> по основным ребрам, нужно найти в <tex>path</tex> наименее значимый единичный бит. Формула <tex>\dfrac12(x \oplus (x - 1)) + 1</tex> имеено это и делает.
 
}}
 
}}
  
Строка 113: Строка 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> действий для ответа на запрос.
 +
 
 +
== См.также ==
 +
*[[Алгоритм Тарьяна поиска LCA за O(1) в оффлайн ]]
 +
*[[Метод двоичного подъема]]
 +
== Источники информации ==
 +
* [http://ia600208.us.archive.org/12/items/onfindinglowe00schi/onfindinglowe00schi.pdf Baruch Schieber, Uzi Vishkin, "On Finding Lowest Common Ancestors: Simplification and Parallelization"]
  
==Ссылки==
+
[[Категория: Дискретная математика и алгоритмы]]
[http://ia600208.us.archive.org/12/items/onfindinglowe00schi/onfindinglowe00schi.pdf Оригинальная статья]
+
[[Категория: Задача о наименьшем общем предке]]

Текущая версия на 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] действий для ответа на запрос.

См.также

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