Изменения
→Обработка запроса
==Обработка запроса==
Пусть <tex>x</tex>, <tex>y</tex> {{---}} вершины в исходном дереве <tex>LCA</tex> которых необходимо найти. Если <tex>\operatorname{inlabel} x = \operatorname{inlabel} y</tex>, то они принадлежат одному простому пути, а следовательно ответом на запрос является <tex>x</tex>, если <tex>\operatorname{level} x \le \operatorname{level} y</tex>, и <tex>y</tex>, в противном случае. Теперь рассмотрим случай, когда <tex>\operatorname{inlabel} x \ne \operatorname{inlabel} y</tex>, то есть <tex>x</tex> и <tex>y</tex> принадлежат разным простым путям. Найдем <tex>b = LCA(\operatorname{inlabel} x, \operatorname{inlabel} y)</tex>.
Сначала найдем <tex>LCA(\operatorname{inlabel} x, \operatorname{inlabel} y)</tex> по каркасным ребрам. Для этого вомпользуемся посчитанными значениями <tex>\operatorname{ascendant} v</tex>. После этого найдем <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\frac{(\operatorname{ascendant} x) \wedge (\operatorname{ascendant} y)}{2^i}\rfloor</tex>
#<tex>LCA(\operatorname{inlabel} LCA(x, \operatorname{inlabel} y) \leftarrow \lfloor\frac12(path \oplus (path - 1))\rfloor + 1</tex>
|proof=<tex>\operatorname{inlabel} x</tex> и <tex>\operatorname{inlabel} y</tex> {{---}} вершины в <tex>B</tex>. Биты в их записи задают задают их местоположение в дереве.
Ноль {{---}} спуститься влево, единица {{---}} спуститься вправо или остаться здесь. Значит, наиболее значимый бит побитового исключающего или их номеров даст глубину, на которой пути до этих вершин начинают расходиться. Это и хранится в <tex>i</tex>.
