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

** 'Solutie $O(M*log^2^(N))$':heavy-path-decomposition#solutie-descompunere

** 'Solutia $O(M*log(N)*sqrt(N))$':heavy-path-decomposition#soluti-log-sqrt
** 'Solutie $O(M*log^2^(N))$':heavy-path-decomposition#solutie-log-log

* '{*} Aplicatii':heavy-path-decomposition#aplicatii
* '{*} Bibliografie':heavy-path-decomposition#bibliografie

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 $depth[]$ ce retine adancimea, adica numarul de muchii de la radacina pana la nodul interogat. Cu ajutorul lor, urmatorul pseudocod rezolva primul tip de cerinta:

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 $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 valoare maxima ceruta. Rezolvarea cerintei a doua se face simplu in $O(1)$ modificand direct $value[]$.

== code(c) |
QUERY(x, y)
    ret = Maxim(value[x], value[y]);
    cat timp x diferit de y executa
        daca depth[x] > depth[y] atunci
            x = parent[x];
            ret = Maxim(ret, value[x]);
        altfel
            y = parent[y];
            ret = Maxim(ret, value[y]);
        sfarsit daca
    sfarsit cat timp
    returneaza ret;
==
 
Rezolvarea cerintei a doua se face simplu in $O(1)$ modificand direct $value[]$.
 
h3(#solutie-descompunere). Solutia $O(M*log^2^(N))$
 
Voi prezenta intr-un mod indirect cum se ajunge la aceasta complexitate, intrucat exista o solutie relativ asemanatoare celei pe care mi-am propus sa o prezint, insa nu la fel de rapida, numita $longest path decomposition$. Si, desigur, nu este rau daca stim ceva in plus. :)

h3(#solutie-log-sqrt). Solutia $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 brute force prezentata mai sus.

Insa, cu $longest path decomposition$, tehnica ce necesita cunostine minime despre grafuri, vom obtine complexitatea $O(M*sqrt(N)*log(N))$ urmand pasii de mai jos:

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

==
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 $lca$ fiind cel mai apropiat stramos comun al lui $x$ si $y$.

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.

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

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 din figura urmatoare:

h3(#solutie-log-log). Solutia $O(M*log^2^(N))$
 
O imbunatatire la solutia 'precedenta':heavy-path-decomposition#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:

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

Complexitatea finala: $O(M log^2^(N))$. In practica, aceasta tehnica se comporta foarte bine si poate fi folosita cu succes. Singurul inconvenient este numarul mare de linii de cod scrie.

h2(#aplicatii). Aplicatii