Изменения
→Препроцессинг
<tex>\operatorname{preOrder} u \in [\operatorname{preOrder} v; \operatorname{preOrder}v + \operatorname{size} v - 1]</tex>
|proof=
По определению <tex>\operatorname{preOrder}</tex>, : <tex>\operatorname{preOrder} u</tex> вершин из поддерева <tex>v</tex> образуют
отрезок натуральных чисел длиной <tex>\operatorname{size} v - 1</tex>. Так как этот отрезок начинается с
<tex>\operatorname{preOrder}v + 1</tex>, то <tex>\operatorname{preOrder} u</tex> лежит в отрезке <tex>[\operatorname{preOrder} v; \operatorname{preOrder} v + \operatorname{size} v - 1]</tex>.
