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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Подготовка)
Строка 11: Строка 11:
  
 
==Подготовка==
 
==Подготовка==
 +
{{Определение
 +
|definition=
 +
<tex>T</tex> {{---}} входное дерево с <tex>n</tex> вершинами. Для него нужно отвечать на запросы <tex>LCA</tex>.<br>
 +
<tex>B</tex> {{---}} полное двоичное дерево с не менее, чем <tex>n</tex> вершинами. Будет введено и объяснено дальше.<br>
 +
<tex>u \in S(v)</tex> {{---}} вершина <tex>v</tex> находится в поддереве вершины <tex>v</tex>. Здесь и далее считаем, что вершина является и своим предком, и своим потомком.<br>
 +
<tex>v</tex> ''выше'' <tex>u</tex> {{---}} то же самое, что <tex>u \in S(v)</tex>. Корень выше любой вершины.
 +
}}
 +
 
Перенумеруем вершины в порядке префиксного обхода дерева: сначала обрабатывается текущая вершина, затем {{---}} поддеревья.
 
Перенумеруем вершины в порядке префиксного обхода дерева: сначала обрабатывается текущая вершина, затем {{---}} поддеревья.
 
Пусть <tex>\operatorname{order} : V \to \mathbb{N}</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>.  
что вершина является и своим предком, и своим потомком.
 
 
 
{{Определение
 
|definition=<tex>u \in S(v)</tex> {{---}} вершина <tex>v</tex> находится в поддереве вершины <tex>v</tex>
 
}}
 
  
 
{{Утверждение
 
{{Утверждение
Строка 36: Строка 39:
 
|proof=
 
|proof=
 
Пусть <tex>\operatorname{inlabel} v = \operatorname{order} u = k2^b</tex>, <tex>b</tex> {{---}} максимально.
 
Пусть <tex>\operatorname{inlabel} v = \operatorname{order} u = k2^b</tex>, <tex>b</tex> {{---}} максимально.
Пусть есть вершина <tex>u' \in S(i)</tex> такая, что <tex>\operatorname{order} u' = k'2^b</tex>.
+
Пусть есть вершина <tex>u' \in S(v)</tex> такая, что <tex>\operatorname{order} 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>\operatorname{order} u \hdots 2^{max}</tex>.
+
Значит, в поддереве <tex>v</tex> есть только одна такая вершина <tex>u</tex>, что <tex>2^{max} | \operatorname{order} u</tex>.
  
 
Рассмотрим два случая.  
 
Рассмотрим два случая.  
Строка 48: Строка 51:
 
от <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>\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>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>. Так как отрезки, соответствующие поддеревьям сыновей, не пересекаются, не найдется другого <tex>w'</tex> {{---}} потомок <tex>v</tex>, что в поддереве <tex>w'</tex> есть вершина с такой же степенью двойки. Значит, все вершины <tex>v'</tex>, у которых <tex>\operatorname{inlabel} v' = \operatorname{inlabel} v</tex> находятся в поддереве <tex>w</tex>. Проведя аналогичное доказательство для <tex>w</tex>, получим требуемое.
+
 
 +
Получили, что прообраз <tex>\operatorname{inlabel} v</tex> в вершине <tex>v</tex> или обрывается, или продолжается вниз ровно в одного потомка. Значит, прообраз <tex>\operatorname{inlabel} v</tex> {{---}} цепочка из какой-то вершины вниз в <tex>T</tex>, что и требовалось доказать.
 
}}
 
}}
  
 
{{Утверждение
 
{{Утверждение
|statement=<tex>\operatorname{inlabel} v = 2^i (\frac{\operatorname{order} v + \operatorname{size} v}{2^i})</tex>, где <tex>i = \lfloor\log_2 (\operatorname{order} v \oplus (\operatorname{order} v + \operatorname{size} v)) \rfloor + 1</tex>
+
|statement=<tex>\operatorname{inlabel} v = 2^i (\frac{\operatorname{order} v + \operatorname{size} v}{2^i})</tex>, где <tex>i = \lfloor\log_2 ((\operatorname{order} - 1) v \oplus (\operatorname{order} v + \operatorname{size} v - 1)) \rfloor + 1</tex>
 
|proof=
 
|proof=
Посмотрим на <tex>A = \operatorname{order} v \oplus (\operatorname{order} v + \operatorname{size} v)</tex>.  
+
Посмотрим на <tex>A = (\operatorname{order} v - 1) \oplus (\operatorname{order} v + \operatorname{size} v - 1)</tex>.  
Посмотрим на позицию самой правой единицы <tex>l</tex> в <tex>A</tex>.  
+
Посмотрим на позицию самго значимого единичного бита <tex>l</tex> в <tex>A</tex>.  
  
Так как в <tex>\operatorname{order} v</tex> там еще <tex>0</tex>, а в <tex>\operatorname{order} v + \operatorname{size} v</tex> {{---}} уже единица, то в отрезке <tex>[\operatorname{order} v; \operatorname{order} v + \operatorname{size} v]</tex> есть число, кратное <tex>2^l</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>2^{l+1}</tex>. Пусть такое число нашлось. Тогда <tex>l</tex>-й бит менялся хотя бы два раза, а значит, менялся  
 
Докажем, что нет чисел, кратных <tex>2^{l+1}</tex>. Пусть такое число нашлось. Тогда <tex>l</tex>-й бит менялся хотя бы два раза, а значит, менялся  
<tex>l+1</tex>-й бит. А значит, самый значащий отличающийся бит в <tex>\operatorname{order} v</tex> и в <tex>\operatorname{order} v + \operatorname{size} v</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>\lfloor \log_2 a \rfloor + 1</tex> просто выделяет номер самого значашего единичного бита.
 
Заметим, что функция <tex>\lfloor \log_2 a \rfloor + 1</tex> просто выделяет номер самого значашего единичного бита.
Строка 70: Строка 74:
 
}}
 
}}
  
Каждое значение <tex>\operatorname{inlabel} v</tex> соответствует вершине в полном двоичном дереве высоты <tex>h=\lceil\log_2 n\rceil</tex>. В двоичном дереве будем нумеровать вершины в инфиксном порядке: обойдем левое поддерево, занумеруем вершину, обойдем правое поддерево. В двоичном дереве будет ребро между вершинами <tex>\operatorname{inlabel} v</tex> и <tex>\operatorname{inlabel} u</tex>, если в начальном дереве есть ребро <tex>v\to 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> по каркасным ребрам.
ребер не будет. Они нужны только для того, чтобы занумеровать вершины и для следующего утверждения.
 
  
 
{{Утверждение
 
{{Утверждение
|statement=Если в начальном дереве есть ребро <tex>v\to u</tex> (<tex>u \in S(v)</tex>), то в построенном двоичном дереве
+
|statement=Если в <tex>T</tex> есть ребро <tex>v\to u</tex>, то в <tex>B</tex>: <tex>\operatorname{inlabel} u \in S(\operatorname{inlabel} v)</tex>
<tex>\operatorname{inlabel} u \in S(\operatorname{inlabel} v)</tex>
+
Другими словами, все основные ребра направлены вниз.
 
|proof=
 
|proof=
 
}}
 
}}
  
Посчитаем для каждого <tex>\operatorname{inlabel} 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>\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{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>.
  
 
==Обработка запроса==
 
==Обработка запроса==

Версия 20:28, 23 июня 2012

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

[math]v[/math] выше [math]u[/math] — то же самое, что [math]u \in S(v)[/math]. Корень выше любой вершины.


Перенумеруем вершины в порядке префиксного обхода дерева: сначала обрабатывается текущая вершина, затем — поддеревья. Пусть [math]\operatorname{order} : V \to \mathbb{N}[/math] — такой порядок обхода.

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

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

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

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

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

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

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

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

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

Докажем, что нет чисел, кратных [math]2^{l+1}[/math]. Пусть такое число нашлось. Тогда [math]l[/math]-й бит менялся хотя бы два раза, а значит, менялся [math]l+1[/math]-й бит. А значит, самый значащий отличающийся бит в [math]\operatorname{order} v - 1[/math] и в [math]\operatorname{order} v + \operatorname{size} v - 1[/math] больше, чем [math]l[/math]-й.

Заметим, что функция [math]\lfloor \log_2 a \rfloor + 1[/math] просто выделяет номер самого значашего единичного бита.

Функция [math]2^l\frac{a}{2^l}[/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]x[/math], [math]y[/math] — вершины в исходном дереве [math]LCA[/math] которых необходимо найти. Если [math]\operatorname{inlabel} x = \operatorname{inlabel} y[/math], то они принадлежат одному простому пути, а следовательно ответом на запрос является [math]x[/math], если [math]\operatorname{level} x \le \operatorname{level} y[/math], и [math]y[/math], в противном случае. Теперь рассмотрим случай, когда [math]\operatorname{inlabel} x \ne \operatorname{inlabel} y[/math], то есть [math]x[/math] и [math]y[/math] принадлежат разным простым путям. Найдем [math]b = LCA(\operatorname{inlabel} x, \operatorname{inlabel} y)[/math].

Утверждение:
[math]LCA(\operatorname{inlabel} x, \operatorname{inlabel} y) = 2^i((2(\frac x{2^{i+1}})) \,|\, 1)[/math], где [math]i = \log(\operatorname{inlabel} x \oplus \operatorname{inlabel} y)[/math]
[math]\triangleright[/math]
Пусть [math]i[/math] — индекс самой правой единицы в двоичном представлении [math]b[/math]. Из того, что [math]b[/math] общий предок [math]\operatorname{inlabel} x[/math] и [math]\operatorname{inlabel} y[/math] в полном двоичном дереве следует, что [math]l-i[/math] левых бит, совпадающих в [math]\operatorname{inlabel} x[/math] и [math]\operatorname{inlabel} y[/math], должны быть такими же и в [math]b[/math], а так как [math]b[/math] наименьший общий предок, то [math]i[/math] — минимальный такой индекс. То есть [math]i[/math] самый левый бит, в котором различаются [math]\operatorname{inlabel} x[/math] и [math]\operatorname{inlabel} y[/math]. А двоичное представление [math]b[/math] состоит из [math]l-i[/math] левых бит [math]\operatorname{inlabel} x[/math] (или [math]\operatorname{inlabel} y[/math]), единички и [math]i[/math] нулей.
[math]\triangleleft[/math]

Найдем вершину [math]\operatorname{inlabel} z[/math], где [math]z = LCA(x, y)[/math]. На прошлом шаге была найдена вершина [math]LCA(\operatorname{inlabel} x, \operatorname{inlabel} y)[/math]. Если бы в двоичном дереве были представлены все вершины, то это и было бы ответом. Но такой вершины может не оказаться. Воспользуемся значениями [math]\operatorname{ascendant} \operatorname{inlabel} x[/math] и [math]\operatorname{ascendant} \operatorname{inlabel} y[/math]. Они характеризуют пути из вершин [math]\operatorname{inlabel} x[/math] и [math]\operatorname{inlabel} x[/math] к корню. С их помощью (с помощью операции логическое и), можно получить список вершин, через которые проходят оба эти пути и взять с пересечения самую низкую посещаемую обоими.

Для этого можно воспользоваться описанным при построении методом для нахождения [math]\operatorname{inlabel} v[/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]O(n)[/math]. Это можно сделать, например, обходом в глубину.

Запрос

Здесь нужно сделать [math]O(1)[/math] действий для ответа на запрос.