(Creat de '_wickedman_':user/wickedman la data de _2004-11-08_ categoria _Arbori_, autor(i) _Miron Emilian_)
*Continut scurt:*

 ==Include(page="template/raw")==
 
Problema luata in discutie este ca, avand un arbore dat sa putem raspunde rapid la multe intrebari de genul care este stramosul comun cel mai apropiat dintre doua noduri din arbore.

 Problema luata in discutie este ca, avand un arbore dat sa putem raspunde rapid la multe intrebari de genul care este stramosul comun cel mai apropiat dintre doua noduri din arbore.

*Continut lung:*

==Include(page="template/raw")==
 

Problema luata in discutie este ca, avand un arbore dat sa putem raspunde rapid la multe intrebari de genul care este stramosul comun cel mai apropiat dintre doua noduri din arbore.

* agatam arborele intr-un nod oarecare si obtinem un arbore cu radacina.
* pentru fiecare nod precalculam dist[i], reprezentand distanta sa pana la radacina.
* precalculam cele necesare pt LCA.

* raspundem la intrebari de forma d(i,j) prin dist[i] + dist[j] * 2 * dist(lca(i,j)).

* raspundem la intrebari de forma d(i,j) prin dist[i] + dist[j] â?? 2 * dist(lca(i,j)).

* Probleme adhoc care se reduc sau folosesc LCA. (de exemplu problema petrol (baraje Slatina 2003).
Mod de calcul

lca(4,3)=min(adancimi de la pos[4] la pos[3]) = 1

Am redus problema la aflarea minimului intre doua pozitii a unui sir (RMQ * range minimum query). Aceasta subproblema o putem rezolva optim folosind arbori de intervale, sau o metoda folosind spatiu supraliniar (NlgN) a minimelor pe intervale de puteri de 2, incepand de la pozitia i. Timpul de preprocesare este O(N) pentru arbori de intervale si O(NlgN) pentru a doua metoda. Timpul de interogare este O(lgN);
Vom discuta metoda cu spatiu NlgN. Calculam minimele inductiv, pastrand min[i][k] = minimul pe intervalui i..i + 2^k * 1 (de lungime 2^k), si minpos[i][k] pozitia minimului de pe intervalul i..i + 2^k * 1.

Am redus problema la aflarea minimului intre doua pozitii a unui sir (RMQ â?? range minimum query). Aceasta subproblema o putem rezolva optim folosind arbori de intervale, sau o metoda folosind spatiu supraliniar (NlgN) a minimelor pe intervale de puteri de 2, incepand de la pozitia i. Timpul de preprocesare este O(N) pentru arbori de intervale si O(NlgN) pentru a doua metoda. Timpul de interogare este O(lgN);
Vom discuta metoda cu spatiu NlgN. Calculam minimele inductiv, pastrand min[i][k] = minimul pe intervalui i..i + 2^k â?? 1 (de lungime 2^k), si minpos[i][k] pozitia minimului de pe intervalul i..i + 2^k â?? 1.

pt k = 0
min[i][0] = a[i], minpos[i][0] = i;

(minpos[i][k-1] sau minpos[i+2^(k-1)][k-1])
Pentru query intre pozitiile l, r procedam astfel:

Fie k cel mai mare nr astfel incat 2^k <= lungimea intervalului (r * l + 1)

Fie k cel mai mare nr astfel incat 2^k <= lungimea intervalului (r â?? l + 1)

min(l, r) = minim( min[l][k], min[r * 2^k + 1][k])

min(l, r) = minim( min[l][k], min[r â?? 2^k + 1][k])

pozmin(l, r) = pozitia minimului