Изменения
→Препроцессинг
|proof=
Посмотрим на <tex>A = (\operatorname{preOrder} v - 1) \oplus (\operatorname{preOrder} v + \operatorname{size} v - 1)</tex>.
Посмотрим на позицию самго самого значимого единичного бита <tex>l</tex> в <tex>A</tex>.
Так как в <tex>\operatorname{preOrder} v - 1</tex> там еще <tex>0</tex>, а в <tex>\operatorname{preOrder} v + \operatorname{size} v - 1</tex> {{---}} уже единица, то в отрезке <tex>[\operatorname{preOrder} v; \operatorname{preOrder} v + \operatorname{size} v]</tex> есть число, кратное <tex>2^l</tex>.
