Изменения
→Обработка запроса
{{Утверждение
|statement= <tex>LCA(\operatorname{inlabel} LCA(x, \operatorname{inlabel} y) = 2^i((2(\frac x{2^{i+1}})) \,|\, 1)</tex>, где <tex>i = \log(\operatorname{inlabel} x \oplus \operatorname{inlabel} y)</tex>
|proof= Пусть <tex>i</tex> {{---}} индекс самой правой единицы в двоичном представлении <tex>b</tex>. Из того, что <tex>b</tex> общий предок <tex>\operatorname{inlabel} x</tex> и <tex>\operatorname{inlabel} y</tex> в полном двоичном дереве следует, что <tex>l-i</tex> левых бит, совпадающих в <tex>\operatorname{inlabel} x</tex> и <tex>\operatorname{inlabel} y</tex>, должны быть такими же и в <tex>b</tex>, а так как <tex>b</tex> наименьший общий предок, то <tex>i</tex> {{---}} минимальный такой индекс. То есть <tex>i</tex> самый левый бит, в котором различаются <tex>\operatorname{inlabel} x</tex> и <tex>\operatorname{inlabel} y</tex>. А двоичное представление <tex>b</tex> состоит из <tex>l-i</tex> левых бит <tex>\operatorname{inlabel} x</tex> (или <tex>\operatorname{inlabel} y</tex>), единички и <tex>i</tex> нулей.
}}
