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 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.

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.

h2. Enunt
Acum ne vom concentra asupra sarcinii initiale, de determinare a valorii de maxim/minim. Enuntul este urmatorul:

Fie $G = (V, E)$ un graf neorientat conex, $|E| = |V| - 1$. Vom considera, bineinteles, 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 : primul tip cere sa se scrie maximul dintre valorile nodurilor ce se afla pe lantul dintre $x, y &#8712; V$ (daca $P = (x{~0~},x{~1~}, x{~2~}, ..., x{~n~}), x{~0~} = x si x{~n~} = y$,  atunci se cere $&#916; = Maxim {value[u] | u &#8712; P}$), iar al doilea tip modifica valoarea asociata unui nod.

Fie $G = (V, E)$ un graf neorientat conex, $|E| = |V| - 1$. Vom considera, bineinteles, 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:
 
* primul tip cere sa se scrie maximul dintre valorile nodurilor ce se afla pe lantul dintre $x, y &#8712; V$ (daca $P = (x{~0~},x{~1~}, x{~2~}, ..., x{~n~}), x{~0~} = x si x{~n~} = y$,  atunci se cere $&#916; = Maxim {value[u] | u &#8712; P}$)
* al doilea tip modifica valoarea asociata unui nod.

h2. Solutia $O(M*N)$

Este evident ca memoria ocupata este $O(N)$, fiecare nod fiind inclus intr-un singur lant. Numarul maxim de lanturi prin care putem trece pornind din radacina pana intr-una din frunze, este $O(sqrt(N))$.

_Fig. 2 : Cazul defavorabil cand sunt $O(sqrt(N))$ lanturi elementare._

_Fig. 2: Cazul defavorabil cand sunt $O(sqrt(N))$ lanturi elementare._

!heavy-path-decomposition?Figura2.jpg!

O imbunatatire pentru aceasta metoda o reprezinta $heavy path decomposition$, care se foloseste de acelasi algoritm, cu exceptia faptului ca fiul ales pentru determinarea unui lant este cel cu numar maxim de noduri in subarborele sau (heavy) si nu cel cu inaltimea maxima (longest). Prin urmare, numarul maxim de lanturi prin care se trece pentru a ajunge de la un nod la radacina este cel mult $O(log(N))$ dupa cum se poate vedea si in figura urmatoare :

_Fig. 3 : Fiecare nod apartine unui singur lant. Lanturile sunt reprezentate de muchii solide._

_Fig. 3: Fiecare nod apartine unui singur lant. Lanturile sunt reprezentate de muchii solide._

!heavy-path-decomposition?Figura3.jpg!

Complexitatea finala : $O(M log^2(N))$. In practica, aceasta tehnica se comporta foarte bine si poate fi folosita cu succes. Singurul dezavantaj este ca trebuie scrise multe linii de cod. Voi incerca sa obtin o solutie cat mai scurta cu _heavy path decomposition_ si o voi atasa acestei pagini pentru cei curiosi. :)

Complexitatea finala: $O(M log^2(N))$. In practica, aceasta tehnica se comporta foarte bine si poate fi folosita cu succes. Singurul dezavantaj este ca trebuie scrise multe linii de cod. Voi incerca sa obtin o solutie cat mai scurta cu _heavy path decomposition_ si o voi atasa acestei pagini pentru cei curiosi. :)

h2. Aplicatii

* "Introducere in algoritmi", autori Thomas H. Cormen, Charles E. Leiserson, Ronald R. Rivest
* "Arbori de intervale si aplicatii in geometrie":arbori-de-intervale, autor Dana Lica
* "Range Minimum Query and Lowest Common Ancestor":http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor, autor Daniel Pasaila

* "LCA : Lowest Common Ancestor":LCA-Lowest-common-ancestor, autor Emilian Miron

* "LCA: Lowest Common Ancestor":LCA-Lowest-common-ancestor, autor Emilian Miron