h2. LCA in $O(sqrt(n))$ (ideea originala de la Radu Berinde)

Daca nu stiti ce este LCA, va recomand sa cititi 'articolul':lca-lowest-common-ancestor lui Emilian Miron din cadrul site-ului pentru a va documenta. In continuare vom prezenta un algoritm mai ineficient, dar foarte usor de implementat. Consideram arborele si atribuim fiecarui nod o inaltime. Vom imparti arborele in $sqrt(H)$ intervale in functie de inaltime, unde $H$ e inaltimea maxima (de exemplu la $H=9$ nodurile cu inaltimi intre $0$ si $2$ vor forma un interval, [{$3..5$}] alt interval si ultimul interval de inaltimi [{$6..8$}]). Astfel, pentru fiecare nod, pe langa tatal sau, vom retine si tatal din intervalul de mai sus, printr-o parcurgere DF. In continuare, codul:

Daca nu stiti ce este LCA, va recomand sa cititi 'articolul':lca-lowest-common-ancestor lui Emilian Miron din cadrul site-ului pentru a va documenta. In continuare vom prezenta un algoritm mai ineficient, dar foarte usor de implementat. Consideram arborele si atribuim fiecarui nod o inaltime. Vom imparti arborele in $sqrt(H)$ intervale in functie de inaltime, unde $H$ e inaltimea maxima (de exemplu la $H=9$ nodurile cu inaltimi intre $0$ si $2$ vor forma un interval, [{$3..5$}] alt interval si ultimul interval de inaltimi [{$6..8$}]). Astfel, pentru fiecare nod, pe langa tatal sau, vom retine si tatal din intervalul de mai sus, printr-o parcurede DF. In continuare, codul:

$H$ se calculeaza inainte sau poate fi constant
$T$ sunt tatii nodului si $N$ numarul de noduri