Изменения
→Подготовка
|statement=В качестве <tex>\operatorname{inlabel} v</tex> можно выбрать <tex>\operatorname{order} u</tex>, кратное максимальной степени двойки, где <tex>u \in S(v)</tex>.
|proof=
Пусть <tex>\operatorname{inorderinlabel} 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>v</tex> есть два числа, кратных <tex>2^b</tex>, то
там есть и число, кратное <tex>2^{b+1}</tex>. Но тогда <tex>\operatorname{inorderinlabel} v</tex> выбран неверно.
Значит, в поддереве <tex>v</tex> есть только одна такая вершина <tex>u</tex>, что <tex>\operatorname{order} u \hdots 2^{max}</tex>.
Рассмотрим два случая.
'''Первый случай''' <tex>\operatorname{inorderinlabel} v = \operatorname{order} v</tex>
Других таких вершин <tex>u'</tex>, что <tex>u'</tex> дает такую же степень двойки, нет.
Значит, во всех поддеревьях <tex>v</tex> значения <tex>\operatorname{inorderinlabel}</tex> отличаютсяот <tex>\operatorname{inorderinlabel} v</tex>.
'''Второй случай''' <tex>\operatorname{inorderinlabel} 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{inorderinlabel} w = \operatorname{inorderinlabel} v = \operatorname{order} u</tex>. Так как отрезки, соответствующие поддеревьям сыновей, не пересекаются, не найдется другого <tex>w'</tex> {{---}} потомок <tex>v</tex>, что в поддереве <tex>w'</tex> есть вершина с такой же степенью двойки. Значит, все вершины <tex>v'</tex>, у которых <tex>\operatorname{inorderinlabel} v' = \operatorname{inorderinlabel} v</tex> находятся в поддереве <tex>w</tex>. Проведя аналогичное доказательство для <tex>w</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>|proof=Посмотрим на <tex>A = \operatorname{order} v \oplus (\operatorname{order} v + \operatorname{size} v)</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>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>\lfloor \log_2 a \rfloor + 1</tex> просто выделяет номер самого значашего единичного бита. Функция <tex>2^l\frac{a}{2^l}</tex> обнуляет все биты младше <tex>l</tex>-го. Чтобы получить из отрезка число, кратное <tex>2^l</tex>, будучи уверенными, что оно там есть, достаточно обнулить <tex>l</tex> битов в правой границе отрезка.
}}
