Изменения
→Подготовка
Обозначим за <tex>\operatorname{size} v</tex> количество вершин в поддереве вершины <tex>v</tex>. Здесь и далее считаем,
что вершина является и своим предком, и своим потомком.
{{Определение
|definition=<tex>u \in S(v)</tex> {{---}} вершина <tex>v</tex> находится в поддереве вершины <tex>v</tex>
}}
{{Утверждение
|statement=Пусть <tex>u</tex> {{---}} вершина из поддерева <tex>\in S(v)</tex>. Тогда
<tex>\operatorname{order} u \in [\operatorname{order} v; \operatorname{order}v + \operatorname{size} v - 1]</tex>
|proof=
По определению <tex>\operatorname{order}</tex>, <tex>\operatorname{order} u</tex> вершин из поддерева <tex>v</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{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>w</tex>, получим требуемое.
}}
