h2. Solutia $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: $seq[]$, $firstPos[]$, $lastPos[]$. Iata pseudocodul acestei parcurgeri :

Solutia se foloseste de o tehnica numita liniarizarea arborelui. Aceasta presupune o parcurgere in adancime si retinerea unor informatii necesare pentru interogare si actualizare: $seq[]$, $firstPos[]$, $lastPos[]$. Iata pseudocodul acestei parcurgeri:

== code(c) |
PARCURGE(x)

Complexitatea finala: $O(M*sqrt(N)*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 in figura urmatoare :

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