* '{*} Aplicatii':tree-decompositions#aplicatii
* '{*} Bibliografie':tree-decompositions#bibliografie

Acest articol prezinta studiul transformarii unui arbore pentru calcularea eficienta a unei insumari si a valorii maxime/minime aflata pe lantul elementar dintre doua noduri. Mentionez ca, in acest articol, $lant$ va insemna intotdeauna $lant elementar$ (un nod poate aparea cel mult odata).

Acest articol prezinta studiul transformarii unui arbore pentru calcularea eficienta a unei insumari si a valorii maxime/minime aflate pe lantul elementar dintre doua noduri. Mentionez ca, in acest articol, $lant$ va insemna intotdeauna $lant elementar$ (un nod poate aparea cel mult odata).

h2(#liniarizare). Liniarizare
Un enunt care apare frecvent la concursurile de informatica este urmatorul:

Fie <tex> G = (V, E) </tex> un graf neorientat conex, <tex> |E| = |V| - 1 </tex> (pe scurt, un arbore). Vom considera ca fiecare nod <tex> x \in V </tex> are asociata o valoare <tex> value[x] </tex> din multimea numerelor reale. Se dau $M$ instructiuni, $M <= 200000$, de doua tipuri:

Fie <tex> G = (V, E) </tex> un graf neorientat conex, <tex> |E| = |V| - 1 </tex> (pe scurt, un arbore). Vom considera ca fiecare nod <tex> x \in V </tex> are asociata o valoare <tex> value[x] </tex> din multimea numerelor reale. Se dau $M$ instructiuni, $M &le; 200000$, de doua tipuri:

* primul tip cere sa se afiseze suma valorilor tuturor nodurilor ce se afla pe lantul dintre <tex> x, y \in V </tex> (practic, daca <tex> P = (x_{0}, x_{1}, x_{2}, ..., x_{n}), x_{0} = x, x_{n} = y </tex>, este lantul ce uneste cele doua noduri, atunci se cere <tex> \Delta = \displaystyle\sum_{u \in P} value[u] </tex>
* al doilea tip modifica valoarea atasata unui nod.

Acum ne vom concentra asupra urmatoarei sarcini, de determinare a valorii de maxim/minim. Sa urmarim enuntul de mai jos.

Fie <tex> G = (V, E) </tex> un graf neorientat conex, <tex> |E| = |V| - 1 </tex> (tot un arbore). Vom considera, bineinteles, ca fiecare nod <tex> x \in V </tex> are asociata o valoare <tex> value[x] </tex> din multimea numerelor reale. Se dau $M$ instructiuni, $M <= 200000$, de doua tipuri:

Fie <tex> G = (V, E) </tex> un graf neorientat conex, <tex> |E| = |V| - 1 </tex> (tot un arbore). Vom considera, bineinteles, ca fiecare nod <tex> x \in V </tex> are asociata o valoare <tex> value[x] </tex> din multimea numerelor reale. Se dau $M$ instructiuni, $M &le; 200000$, de doua tipuri:

* primul tip cere sa se scrie maximul dintre valorile nodurilor ce se afla pe lantul dintre <tex> x, y \in V </tex> (daca <tex> P = (x_{0}, x_{1}, x_{2}, ..., x_{n}), x_{0} = x, x_{n} = y </tex>,  atunci se cere <tex> \Delta = \displaystyle Maxim_{u \in P} value[u] </tex>)
* al doilea tip modifica valoarea asociata unui nod.

h2(#bibliografie). Bibliografie

* "Introducere in algoritmi", autori Thomas H. Cormen, Charles E. Leiserson, Ronald R. Rivest
* "Arbori de intervale si aplicatii in geometrie":arbori-de-intervale, autor Dana Lica
* "Range Minimum Query and Lowest Common Ancestor":http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor, autor Daniel Pasaila
* "LCA: Lowest Common Ancestor":LCA-Lowest-common-ancestor, autor Emilian Miron
* "The level ancestor problem simplified":http://cs.sunysb.edu/~bender/pub/latin02-level.ps, autori Michael A. Bender, Martin Farach-Colton
* "Advanced data structures":http://courses.csail.mit.edu/6.851/spring07/scribe/lec09.pdf, autor Oren Weimann

* Thomas H. Cormen, Charles E. Leiserson, Ronald R. Rivest - _"Introducere in Algoritmi"_
* Dana Lica - "_Arbori de intervale si aplicatii in geometria computationala_":arbori-de-intervale
* Daniel Pasaila - "_Range Minimum Query and Lowest Common Ancestor_":http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor
* 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