_Fig. 1: Pentru arborele din figura alatura si vectorul de valori $value[] = {3, 5, 7, 1, 2, 4}$, $seq[]$ construit este ilustrat mai jos. Se observa usor ca tot subarborele unui nod se anuleaza cand este explorat in intregime._

p=. !heavy-path-decomposition?fig1.jpg!

p=. !heavy-path-decomposition?Figura1.JPG!

Astfel, s-a construit vectorul $seq[]$ care are urmatoarea proprietate : &#34;daca $&#916; = &#8721; seq[i]$, $firstPos[x] <= i <= firstPos[y]$, x fiind un stramos al lui y, atunci &#916; reprezinta $&#8721; value[u]$, $u &#8712; P$, $P = (x{~0~}, x{~1~}, x{~2~}, ..., x{~n~}), x{~0~} = x si x{~n~} = y&#34;$. Conform acesteia, daca vom determina cel mai apropiat stramos comun dintre doua noduri, atunci nu va fi nevoie decat de un cost cat mai mic pentru calcularea eficienta a sumei pe un interval si modificarea unei valori din acest vector $seq[]$. Cu ajutorul structurii de date numita arbori de intervale putem obtine costul $O(log(N))$ pe fiecare din cele doua operatii. Pentru determinarea eficienta a celui mai apropiat stramos comun consultati bibliografia.