lastPos[x] = seq_len;
==

_Fig. 1: Pentru arborele din figura de mai jos 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._

_Fig. 1: Pentru arborele din figura de mai jos si vectorul de valori_ <tex> value[] = \{3, 5, 7, 1, 2, 4\} </tex>, <tex> seq[] </tex> _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!

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.

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':heavy-path-decomposition#bibliografie.

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

h3(#solutie-descompunere-brute). Solutia $O(M*N)$

Sunt o multitudine de solutii simple ce ne pot trece prin minte. Pentru cea aleasa de mine voi retine un vector $parent[]$ semnificand parintele unui nod calculat printr-un $depth-search$, si un vector $depth[]$ ce retine adancimea, adica numarul de muchii de la radacina pana la nodul interogat. Cu ajutorul lor, prima cerinta se rezolva in $O(N)$ astfel: merg "in sus" in arbore pana cand voi ajunge in cel mai apropiat stramos comun, retinand pe parcurs valoarea maxima ceruta. Rezolvarea cerintei a doua se face simplu in $O(1)$ modificand direct <tex> value[] </tex>.

Sunt o multitudine de solutii simple ce ne pot trece prin minte. Pentru cea aleasa de mine voi retine un vector <tex> parent[] </tex> semnificand parintele unui nod calculat printr-un $depth-search$, si un vector <tex> depth[] </tex> ce retine adancimea, adica numarul de muchii de la radacina pana la nodul interogat. Cu ajutorul lor, prima cerinta se rezolva in $O(N)$ astfel: merg "in sus" in arbore pana cand ajung in cel mai apropiat stramos comun, retinand pe parcurs valoarea maxima ceruta. Rezolvarea cerintei a doua se face simplu in $O(1)$ modificand direct <tex> value[] </tex>.

h3(#solutie-log-sqrt). Solutia $O(M*log(N)*sqrt(N))$

Aceasta solutie foloseste asa numita tehnica $longest path decomposition$, tehnica ce necesita cunostine minime despre grafuri si cu care vom obtine complexitatea $O(M*sqrt(N)*log(N))$ urmand pasii de mai jos:
# Elimina cel mai lung lant radacina-frunza din arbore si apeleaza recursiv pentru restul componentelor conexe;

# Retine fiecare lant ca un vector $Path[].array[]$ cu noduri ordonate crescator dupa adancime si pastreaza un pointer catre nodul din lantul sau parinte $Path[].parent$;
# Pentru fiecare nod retine lantul caruia apartine $whatPath[]$ si pozitia in vectorul lantului $whatPos[]$.

# Retine fiecare lant ca un vector <tex> Path[].array[] </tex> cu noduri ordonate crescator dupa adancime si pastreaza un pointer catre nodul din lantul sau parinte <tex> Path[].parent </tex>;
# Pentru fiecare nod retine lantul caruia apartine <tex> whatPath[] </tex> si pozitia in vectorul lantului <tex> whatPos[] </tex>.

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

==
Functia $QUERYAi(Path[], lo, hi)$ returneaza in $O(log(N))$, cu ajutorul structurii de date arbori de intervale, maximul dintre valorile cuprinse in intervalul $[lo, hi]$.
Raspunsul cerintei de primul tip va fi  {$Maxim(QUERY (lca, x), QUERY (lca, y))$}, variabila <tex> lca </tex> fiind cel mai apropiat stramos comun al lui <tex> x </tex> si <tex> y </tex>.

Pentru rezolvarea cerintei de tipul doi, vom folosi aceiasi arbori de intervale care vor obtine un cost de $O(log(N))$ pe operatie. Nu voi prezenta aceasta functie, ea fiind in detaliu prezentata in una din sursele afisate in 'Bibliografie':heavy-path-decomposition#bibliografie.

Pentru rezolvarea cerintei de tipul doi, vom folosi aceiasi arbori de intervale care vor obtine un cost de $O(log(N))$ pe operatie. Nu voi prezenta aceasta functie, ea fiind in detaliu prezentata in una din sursele afisate in 'bibliografie':heavy-path-decomposition#bibliografie.

Complexitatea finala: $O(M*sqrt(N)*log(N))$. Cel mai rau caz pentru un query este cand se trece prin toate lanturile (in numar de $sqrt(N)$) efectuandu-se cate un query pe fiecare arbore de intervale asociat ({$O(log(N))$}).

h2(#aplicatii). Aplicatii

* "Query on a tree":http://www.spoj.pl/problems/QTREE/ - spoj, 375
* "Caves and tunnels":http://acm.timus.ru/problem.aspx?space=1&num=1553 - timus, Novosibirsk SU Contest, Petrozavodsk training camp, September 2007
* "Delay":problema/delay - pregatirea lotului national de informatica, 2002.
* "Omizi":problema/omizi - .campion 2005
* "Arbfind":problema/arbfind - pregatirea lotului national de informatica, 2006.
* "CT":problema/ct - Happy Coding 2006

* "Query on a tree":http://www.spoj.pl/problems/QTREE/
* "Caves and tunnels":http://acm.timus.ru/problem.aspx?space=1&num=1553 - Petrozavodsk training camp, September, 2007
* "Delay":problema/delay - Lotul national de informatica, 2002
* "Omizi":problema/omizi - .campion, 2005
* "Arbfind":problema/arbfind - Lotul national de informatica, 2006
* "CT":problema/ct - Happy Coding, 2006

h2(#bibliografie). Bibliografie