Un enunt care apare frecvent la concursurile de informatica este urmatorul:

Fie $G = (V, E)$ un graf neorientat conex, $|E| = |V| - 1$ (pe scurt, un arbore). Vom considera ca fiecare nod $x &#8712; V$ are asociata o valoare $value[x]$ din multimea numerelor reale. Se dau $M$ instructiuni, $M <= 200000$, de doua tipuri:

Fie <tex> G = (V, E) </tex> un graf neorientat conex, <tex> |E| = |V| - 1 </tex> (pe scurt, un arbore). Vom considera ca fiecare nod <tex> x \in V </tex> are asociata o valoare <tex> value[x] </tex> din multimea numerelor reale. Se dau $M$ instructiuni, $M <= 200000$, de doua tipuri:

* primul tip cere sa se afiseze suma valorilor tuturor nodurilor ce se afla pe lantul dintre $x, y ∈ V$ (practic, daca $P = (x{~0~},x{~1~}, x{~2~}, ..., x{~n~}), x{~0~} = x si x{~n~} = y$, este lantul ce uneste cele doua noduri, atunci se cere $Δ = ∑ value[u]$, $u ∈ P$)

* primul tip cere sa se afiseze suma valorilor tuturor nodurilor ce se afla pe lantul dintre <tex> x, y \in V </tex> (practic, daca <tex> P = (x_{0}, x_{1}, x_{2}, ..., x_{n}), x_{0} = x, x_{n} = y </tex>, este lantul ce uneste cele doua noduri, atunci se cere <tex> \Delta = \displaystyle\sum_{u \in P} value[u] </tex>

* al doilea tip modifica valoarea atasata unui nod.
h3(#solutie-liniarizare). Solutia $O((M+N)*log(N))$

Solutia se foloseste de o tehnica numita liniarizarea arborelui. Aceasta presupune o parcurgere in adancime si retinerea unor informatii necesare pentru interogare si actualizare: $seq[]$, $firstPos[]$, $lastPos[]$. Iata pseudocodul acestei parcurgeri:

Solutia se foloseste de o tehnica numita liniarizarea arborelui. Aceasta presupune o parcurgere in adancime si retinerea unor informatii necesare pentru interogare si actualizare: <tex> seq[] </tex>, <tex> firstPos[] </tex>, <tex> lastPos[] </tex>. Iata pseudocodul acestei parcurgeri:

== code(c) |
PARCURGE(x)

p=. !heavy-path-decomposition?fig1.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 o structura de date ce permite calcularea intr-un mod eficient a sumei pe un interval din $seq[]$ si modificarea unei valori din acest vector. Putem obtine complexitatea $O(log(N))$ pe fiecare din cele doua operatii folosind structura de date numita arbori de intervale. Pentru determinarea eficienta a celui mai apropiat stramos comun si pentru detalii despre arborii de intervale consultati bibliografia.

Astfel, s-a construit vectorul <tex> seq[] </tex> care are urmatoarea proprietate: &#34;daca <tex> \Delta = \displaystyle\sum_{i = firstPos[x]}^{firstPos[y]} seq[i] </tex>, <tex> x </tex> fiind un stramos al lui <tex> y </tex>, atunci <tex> \Delta </tex> reprezinta <tex> \Delta = \displaystyle\sum_{u \in P} value[u] </tex>, <tex> P = (x_{0}, x_{1}, x_{2}, ..., x_{n}), x_{0} = x, x_{n} = y </tex>&#34;. Conform acesteia, daca vom determina cel mai apropiat stramos comun dintre doua noduri, atunci nu va fi nevoie decat de o structura de date ce permite calcularea intr-un mod eficient a sumei pe un interval din <tex> seq[] </tex> si modificarea unei valori din acest vector. Putem obtine complexitatea $O(log(N))$ pe fiecare din cele doua operatii folosind structura de date numita arbori de intervale. Pentru determinarea eficienta a celui mai apropiat stramos comun si pentru detalii despre arborii de intervale consultati bibliografia.

h2(#descompunere-in-lanturi). Descompunere in lanturi