Изменения
Нет описания правки
{{Утверждение
|statement=<tex>\operatorname{inlabel} v = 2^i (\lfloor\frac{\operatorname{order} v + \operatorname{size} v}{2^i})\rfloor</tex>, где <tex>i = \lfloor\log_2 ((\operatorname{order} - 1) v \oplus (\operatorname{order} v + \operatorname{size} v - 1)) \rfloor + 1</tex>
|proof=
Посмотрим на <tex>A = (\operatorname{order} v - 1) \oplus (\operatorname{order} v + \operatorname{size} v - 1)</tex>.
#<tex>i \leftarrow \lfloor\log_2 (\operatorname{inlabel} x \oplus \operatorname{inlabel} y)\rfloor</tex>
#<tex>path \leftarrow 2^i \lfloor\frac{(\operatorname{ascendant} x) \wedge (\operatorname{ascendant} y)}{2^i}\rfloor</tex>#<tex>LCA(\operatorname{inlabel} x, \operatorname{inlabel} y) \leftarrow \lfloor\frac12(path \oplus (path - 1)) \rfloor + 1</tex>
|proof=<tex>x</tex> и <tex>y</tex> {{---}} вершины в <tex>B</tex>. Биты в их записи задают задают их местоположение в дереве.
Ноль {{---}} спуститься влево, единица {{---}} спуститься вправо или остаться здесь. Значит, наиболее значимый бит побитового исключающего или их номеров даст глубину, на которой пути до этих вершин начинают расходиться. Это и хранится в <tex>i</tex>.
