(Categoria _Algoritmi_, Autor _Marius Stroe_)
(toc){width: 20em}*{text-align:center} *Continut:*

* '{*} Liniarizare':tree-decompositions#liniarizare
** '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-descompunere-brute
** 'Solutia $O(M*log(N)*sqrt(N))$':tree-decompositions#solutie-log-sqrt
** 'Solutie $O(M*log^2^(N))$':tree-decompositions#solutie-log-log
* '{*} Aplicatii':tree-decompositions#aplicatii
* '{*} Bibliografie':tree-decompositions#bibliografie

* 'Liniarizare':tree-decompositions#liniarizare
** '{*} 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*log^2^(N))$':tree-decompositions#solutie-log-log
* 'Aplicatii':tree-decompositions#aplicatii
* 'Bibliografie':tree-decompositions#bibliografie

Acest articol prezinta studiul transformarii unui arbore pentru calcularea eficienta a unei insumari si a valorii maxime/minime aflate pe lantul elementar dintre doua noduri. Mentionez ca, in acest articol, $lant$ va insemna intotdeauna $lant elementar$ (un nod poate aparea cel mult odata).

Acest articol prezinta studiul transformarii unui arbore pentru calcularea eficienta a unei insumari si a valorii maxime / minime aflate pe lantul elementar dintre doua noduri. Mentionez ca, in acest articol, $lant$ va insemna intotdeauna $lant elementar$ (un nod poate aparea cel mult o data).

h2(#liniarizare). Liniarizare

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

h3(#solutie-liniarizare). Solutie $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: <tex> seq[] </tex>, <tex> firstPos[] </tex>, <tex> lastPos[] </tex>. Iata pseudocodul acestei parcurgeri:

* primul tip 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 = \displaystyle Maxim_{u \in P} value[u] </tex>)
* al doilea tip modifica valoarea asociata unui nod.

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

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

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

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

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). Solutia $O(M*log^2^(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: