Изменения

Обозначим за <tex>\operatorname{size} v</tex> количество вершин в поддереве вершины <tex>v</tex>. Здесь и далее считаем, что вершина является и своим предком, и своим потомком. {{Определение|definition=<tex>u \in S(v)</tex> {{---}} вершина <tex>v</tex> находится в поддереве вершины <tex>v</tex>}}

Пусть есть вершина <tex>u' \in S(iv)</tex> такая, что <tex>\operatorname{order} u' = k'2^b</tex>.

Значит, в поддереве <tex>v</tex> есть только одна такая вершина <tex>u</tex>, что <tex>2^{max} | \operatorname{order} u \hdots 2^{max}</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>. Так как отрезки, соответствующие поддеревьям сыновей, не пересекаются, не найдется другого <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>wT</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>

Посмотрим на <tex>A = (\operatorname{order} v - 1) \oplus (\operatorname{order} v + \operatorname{size} v- 1)</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>l+1</tex>-й бит. А значит, самый значащий отличающийся бит в <tex>\operatorname{order} v- 1</tex> и в <tex>\operatorname{order} v + \operatorname{size} v- 1</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> по каркасным ребрам.

|statement=Если в начальном дереве <tex>T</tex> есть ребро <tex>v\to u</tex> (, то в <tex>u \in S(v)B</tex>), то в построенном двоичном дереве: <tex>\operatorname{inlabel} u \in S(\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>\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>.