** '{*} Solutie $O((M+N)*log(N))$':tree-decompositions#solutie-liniarizare
* 'Descompunere in lanturi':tree-decompositions#descompunere-in-lanturi
** '{*} Solutie $O(M*N)$':tree-decompositions#solutie-brute

** '{*} Solutie $O(M*log(N)*sqrt(N))$':tree-decompositions#solutie-log-sqrt

** '{*} Solutie $O(M*sqrt(N)*log(N))$':tree-decompositions#solutie-sqrt-log

** '{*} Solutie $O(M*log^2^(N))$':tree-decompositions#solutie-log-log
* 'Aplicatii':tree-decompositions#aplicatii
* 'Bibliografie':tree-decompositions#bibliografie

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 &le; 200000$, de doua tipuri:

* instructiunile de primul tip cer 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>)

* instructiunile de primul tip cer 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}) </tex>, <tex> x_{0} = x </tex>, <tex> x_{n} = y </tex>, este lantul ce uneste cele doua noduri, atunci se cere <tex> \Delta = \displaystyle\sum_{u \in P} value[u] </tex>)

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

    seq[seq_len] = value[x]
    firstPos[x] = seq_len

    pentru fiecare fiu y al lui x executa

    pentru fiecare fiu nevizitat y al lui x executa

        PARCURGE(y) // apeleaza recursiv pentru y
    sfarsit pentru

Fie <tex> G = (V, E) </tex> un graf neorientat conex, <tex> |E| = |V| - 1 </tex> (tot un arbore). Vom considera, bineinteles, 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 &le; 200000$, de doua tipuri:

* primul tip de instructiuni cere sa se scrie maximul dintre valorile nodurilor ce se afla pe lantul dintre <tex> x, y \in V </tex> (daca <tex> P = (x_{0}, x_{1}, x_{2}, ..., x_{n}), x_{0} = x, x_{n} = y </tex>,  atunci se cere <tex> \Delta = \max \{value[u]\ /\ u \in P \} </tex>)

* primul tip de instructiuni cere sa se scrie maximul dintre valorile nodurilor ce se afla pe lantul dintre <tex> x, y \in V </tex> (daca <tex> P = (x_{0}, x_{1}, x_{2}, ..., x_{n}) </tex>, <tex> x_{0} = x </tex>, <tex> x_{n} = y </tex>,  atunci se cere <tex> \Delta = \max \{value[u]\ /\ u \in P \} </tex>)

* al doilea tip modifica valoarea asociata unui nod.
h3(#solutie-brute). Solutie $O(M*N)$
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-o parcurgere in adancime, 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: pornesc din cele doua noduri si merg "in sus" pe arbore, in paralel (raportat la <tex> depth[\ ] </tex>), 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). Solutie $O(M*log(N)*sqrt(N))$

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

Tehnica liniarizarii arborelui nu ne este de folos in acest caz, deoarece modul de reprezentare a informatiilor nu permite obtinerea unei complexitati mai bune fata de 'solutia lenta':tree-decompositions#solutie-brute prezentata mai sus.

    returneaza ret
==

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 avea 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':tree-decompositions#bibliografie.

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 avea 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':tree-decompositions#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))$}).
h3(#solutie-log-log). Solutie $O(M*log^2^(N))$

O imbunatatire la solutia 'precedenta':tree-decompositions#solutie-log-sqrt 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 din figura urmatoare:

O imbunatatire la solutia 'precedenta':tree-decompositions#solutie-sqrt-log 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 din figura urmatoare:

p=. !tree-decompositions?Figura3.jpg!

* Emilian Miron - "_Lowest Common Ancestor_":lowest-common-ancestor
* Michael A. Bender, Martin Farach-Colton - "_The level ancestor problem simplified_":http://cs.sunysb.edu/~bender/pub/latin02-level.ps
* Oren Weimann - "_Advanced data structures_":http://courses.csail.mit.edu/6.851/spring07/scribe/lec09.pdf

 
h2. Comentarii

2578

3694