Изменения
Нет описания правки
Перенумеруем вершины в порядке префиксного обхода дерева: сначала обрабатывается текущая вершина, затем {{---}} поддеревья.
Пусть <tex>\operatorname{pre-orderpreOrder} : V \to \mathbb{N}</tex> {{---}} такой порядок обхода.
Обозначим за <tex>\operatorname{size} v</tex> количество вершин в поддереве вершины <tex>v</tex>.
{{Утверждение
|statement=Пусть <tex>u \in S(v)</tex>. Тогда
<tex>\operatorname{pre-orderpreOrder} u \in [\operatorname{pre-orderpreOrder} v; \operatorname{pre-orderpreOrder}v + \operatorname{size} v - 1]</tex>
|proof=
По определению <tex>\operatorname{pre-orderpreOrder}</tex>, <tex>\operatorname{pre-orderpreOrder} u</tex> вершин из поддерева <tex>v</tex> образуют
отрезок натуральных чисел длиной <tex>\operatorname{size} v - 1</tex>. Так как этот отрезок начинается с
<tex>\operatorname{pre-orderpreOrder}v + 1</tex>, то <tex>\operatorname{pre-orderpreOrder} u</tex> лежит в отрезке <tex>[\operatorname{pre-orderpreOrder} v; \operatorname{pre-orderpreOrder} v + \operatorname{size} v - 1]</tex>.
}}
{{Утверждение
|statement=В качестве <tex>\operatorname{inlabel} v</tex> можно выбрать <tex>\operatorname{pre-orderpreOrder} u</tex>, кратное максимальной степени двойки, где <tex>u \in S(v)</tex>.
|proof=
Пусть <tex>\operatorname{inlabel} v = \operatorname{pre-orderpreOrder} u = k2^b</tex>, <tex>b</tex> {{---}} максимально.Пусть есть вершина <tex>u' \in S(v)</tex> такая, что <tex>\operatorname{pre-orderpreOrder} u' = k'2^b</tex>.
Так как в отрезке, соответствующем вершине <tex>v</tex> есть два числа, кратных <tex>2^b</tex>, то
там есть и число, кратное <tex>2^{b+1}</tex>. Но тогда <tex>\operatorname{inlabel} v</tex> выбран неверно.
Значит, в поддереве <tex>v</tex> есть только одна такая вершина <tex>u</tex>, что <tex>2^{max} | \operatorname{pre-orderpreOrder} u</tex>.
Рассмотрим два случая.
'''Первый случай''' <tex>\operatorname{inlabel} v = \operatorname{pre-orderpreOrder} v</tex>
Других таких вершин <tex>u'</tex>, что <tex>u'</tex> дает такую же степень двойки, нет.
Значит, во всех поддеревьях <tex>v</tex> значения <tex>\operatorname{inlabel}</tex> отличаются
от <tex>\operatorname{inlabel} v</tex>. '''Второй случай''' <tex>\operatorname{inlabel} v = \operatorname{pre-orderpreOrder} u</tex>, <tex>u \in S(v), u \ne v</tex>. Так как в поддереве <tex>v</tex> представлены все <tex>\operatorname{pre-orderpreOrder}</tex>-ы из отрезка <tex>[\operatorname{pre-orderpreOrder} v; \operatorname{pre-orderpreOrder} 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-orderpreOrder} 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>, что и требовалось доказать.
{{Утверждение
|statement=<tex>\operatorname{inlabel} v = 2^i \lfloor\dfrac{\operatorname{pre-orderpreOrder} v + \operatorname{size} v}{2^i}\rfloor</tex>, где <tex>i = \lfloor\log_2 ((\operatorname{pre-orderpreOrder} - 1) v \oplus (\operatorname{pre-orderpreOrder} v + \operatorname{size} v - 1)) \rfloor + 1</tex>
|proof=
Посмотрим на <tex>A = (\operatorname{pre-orderpreOrder} v - 1) \oplus (\operatorname{pre-orderpreOrder} v + \operatorname{size} v - 1)</tex>.
Посмотрим на позицию самго значимого единичного бита <tex>l</tex> в <tex>A</tex>.
Так как в <tex>\operatorname{pre-orderpreOrder} v - 1</tex> там еще <tex>0</tex>, а в <tex>\operatorname{pre-orderpreOrder} v + \operatorname{size} v - 1</tex> {{---}} уже единица, то в отрезке <tex>[\operatorname{pre-orderpreOrder} v; \operatorname{pre-orderpreOrder} v + \operatorname{size} v]</tex> есть число, кратное <tex>2^l</tex>.
Докажем, что нет чисел, кратных <tex>2^{l+1}</tex>. Пусть такое число нашлось. Тогда <tex>l</tex>-й бит менялся хотя бы два раза, а значит, менялся
<tex>l+1</tex>-й бит. А значит, самый значащий отличающийся бит в <tex>\operatorname{pre-orderpreOrder} v - 1</tex> и в <tex>\operatorname{pre-orderpreOrder} v + \operatorname{size} v - 1</tex> больше, чем <tex>l</tex>-й.
Заметим, что функция <tex>\lfloor \log_2 a \rfloor + 1</tex> просто выделяет номер самого значашего единичного бита.
