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

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

* 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