Изменения
Нет описания правки
Чтобы получить из отрезка число, кратное <tex>2^l</tex>, будучи уверенными, что оно там есть, достаточно обнулить <tex>l</tex> битов в правой границе отрезка.
}}
Каждое значение <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>. Стандартных для двоичного дерева
ребер не будет. Они нужны только для того, чтобы занумеровать вершины и для следующего утверждения.
{{Утверждение
|statement=Если в начальном дереве есть ребро <tex>v\to u</tex> (<tex>u \in S(v)</tex>), то в построенном двоичном дереве
<tex>\operatorname{inorder} u \in S(\operatorname{inorder} v)</tex>
|proof=
}}
Посчитаем для каждого <tex>\operatorname{inlabel} 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>.
==Обработка запроса==
