Изменения

Каждое значение <tex>\operatorname{inlabel} v</tex> соответствует вершине в полном двоичном дереве <tex>B</tex> высоты <tex>h=\lceil\log_2 n\rceil</tex>. В дереве на одном наборе вершин будет построено два набора ребер: ''каркасные'' и ''основные''. Для каждой вершины <tex>v \in V(B)</tex> с уровня, кроме последнего, будут каркасные ребра <tex>v\to2v</tex> и <tex>v\to2v+1</tex>. Таким образом, вершины в <tex>B</tex> будут занумерованы в инфиксном порядке обхода по каркасным ребрам: обход левого поддеревасначала обрабатывается левое поддерево, нумерация вершиныпотом {{---}} вершина, обход правого поддеревапотом {{---}} правое поддерео. В <tex>B</tex> будет основное ребро между вершинами <tex>\operatorname{inlabel} v</tex> и <tex>\operatorname{inlabel} u</tex>, если в <tex>T</tex> есть ребро <tex>v\to u</tex>. Корень имеет номер <tex>1</tex>. Будем говорить, что вершина <tex>u \in B</tex> лежит в поддереве вершины <tex>u \in B</tex> (<tex>u \in S(v)</tex>), если от <tex>v</tex> есть путь до <tex>u</tex> по каркасным ребрам.