!heavy-path-decomposition?Figura2.jpg!

Fie  {$x, y ∈ V, x stramos al lui y$}. Functia care determina valoarea maxima pe lantul dintre $x$ si $y$ este prezentata in urmatorul pseudocod:

Fie  <tex> x, y \in V </tex>, <tex> x </tex> stramos al lui <tex> y </tex>. Functia care determina valoarea maxima pe lantul dintre <tex> x </tex> si <tex> y </tex> este prezentata in urmatorul pseudocod:

== code(c) |
QUERY(x, y)

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

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