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