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