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:
* 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.
* instructiunile de primul tip cer 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>)
* cele de al doilea tip modifica valoarea atasata unui nod.
h3(#solutie-liniarizare). Solutie $O((M+N)*log(N))$
Solutia se foloseste de o tehnica numita liniarizarea arborelui. Aceasta presupune o parcurgere in adancime si retinerea unor informatii necesare pentru interogare si actualizare: <tex> seq[] </tex>, <tex> firstPos[] </tex>, <tex> lastPos[] </tex>. Iata pseudocodul acestei parcurgeri:
Solutia se foloseste de o tehnica numita liniarizarea arborelui. Aceasta presupune o parcurgere in adancime si retinerea unor informatii necesare pentru interogare si actualizare: <tex> seq[\ ] </tex>, <tex> firstPos[\ ] </tex>, <tex> lastPos[\ ] </tex>. Iata pseudocodul acestei parcurgeri:
== code(c) |
PARCURGE(x)
seq_len ++;
seq[seq_len] = value[x];
firstPos[x] = seq_len;
seq_len++
seq[seq_len] = value[x]
firstPos[x] = seq_len
pentru fiecare fiu y al lui x executa
PARCURGE(y); // apeleaza recursiv pentru y
PARCURGE(y) // apeleaza recursiv pentru y
sfarsit pentru
seq_len ++;
seq[seq_len] = -value[x];
lastPos[x] = seq_len;
==
_Fig. 1: Pentru arborele din figura de mai jos si vectorul de valori_ <tex> value[] = \{3, 5, 7, 1, 2, 4\} </tex>, <tex> seq[] </tex> _construit este ilustrat mai jos. Se observa usor ca tot subarborele unui nod se anuleaza cand este explorat in intregime._
seq_len++
seq[seq_len] = -value[x]
lastPos[x] = seq_len
==
p=. !tree-decompositions?fig1.jpg!
Astfel, s-a construit vectorul <tex> seq[] </tex> care are urmatoarea proprietate: "daca <tex> \Delta = \displaystyle\sum_{i = firstPos[x]}^{firstPos[y]} seq[i] </tex>, <tex> x </tex> fiind un stramos al lui <tex> y </tex>, atunci <tex> \Delta </tex> reprezinta <tex> \Delta = \displaystyle\sum_{u \in P} value[u] </tex>, <tex> P = (x_{0}, x_{1}, x_{2}, ..., x_{n}), x_{0} = x, x_{n} = y </tex>". Conform acesteia, daca vom determina cel mai apropiat stramos comun dintre doua noduri, atunci nu va fi nevoie decat de o structura de date ce permite calcularea intr-un mod eficient a sumei pe un interval din <tex> seq[] </tex> si modificarea unei valori din acest vector. Putem obtine complexitatea $O(log(N))$ pe fiecare din cele doua operatii folosind structura de date numita arbori de intervale. Pentru determinarea eficienta a celui mai apropiat stramos comun si pentru detalii despre arborii de intervale consultati 'bibliografia':tree-decompositions#bibliografie.
p=. _Fig. 1: Pentru arborele din figura de mai sus si vectorul de valori_ <tex> value[\ ] = \{3, 5, 7, 1, 2, 4\} </tex>, <tex> seq[\ ] </tex> _construit este ilustrat in figura. Se observa usor ca tot subarborele unui nod se anuleaza cand este explorat in intregime._
Astfel, s-a construit vectorul <tex> seq[\ ] </tex> care are urmatoarea proprietate: "daca <tex> \Delta = \displaystyle\sum_{i = firstPos[x]}^{firstPos[y]} seq[i] </tex>, <tex> x </tex> fiind un stramos al lui <tex> y </tex>, atunci <tex> \Delta </tex> reprezinta <tex> \Delta = \displaystyle\sum_{u \in P} value[u] </tex>, <tex> P = (x_{0}, x_{1}, x_{2}, ..., x_{n}) </tex>, <tex> x_{0} = x </tex>, <tex> x_{n} = y </tex>". Conform acesteia, daca vom determina cel mai apropiat stramos comun dintre doua noduri, atunci nu va fi nevoie decat de o structura de date ce permite calcularea intr-un mod eficient a sumei pe un interval din <tex> seq[\ ] </tex> si modificarea unei valori din acest vector. Putem obtine complexitatea $O(log(N))$ pe fiecare din cele doua operatii folosind structura de date numita arbori de intervale. Pentru determinarea eficienta a celui mai apropiat stramos comun si pentru detalii despre arborii de intervale consultati 'bibliografia':tree-decompositions#bibliografie.
h2(#descompunere-in-lanturi). Descompunere in lanturi
h3(#solutie-brute). Solutie $O(M*N)$
Sunt o multitudine de solutii simple ce ne pot trece prin minte. Pentru cea aleasa de mine voi retine un vector <tex> parent[] </tex> semnificand parintele unui nod calculat printr-un $depth-search$, si un vector <tex> depth[] </tex> ce retine adancimea, adica numarul de muchii de la radacina pana la nodul interogat. Cu ajutorul lor, prima cerinta se rezolva in $O(N)$ astfel: merg "in sus" in arbore pana cand ajung in cel mai apropiat stramos comun, retinand pe parcurs valoarea maxima ceruta. Rezolvarea cerintei a doua se face simplu in $O(1)$ modificand direct <tex> value[] </tex>.
Sunt o multitudine de solutii simple ce ne pot trece prin minte. Pentru cea aleasa de mine voi retine un vector <tex> parent[\ ] </tex> semnificand parintele unui nod calculat printr-un $depth-search$, si un vector <tex> depth[\ ] </tex> ce retine adancimea, adica numarul de muchii de la radacina pana la nodul interogat. Cu ajutorul lor, prima cerinta se rezolva in $O(N)$ astfel: merg "in sus" in arbore pana cand ajung in cel mai apropiat stramos comun, retinand pe parcurs valoarea maxima ceruta. Rezolvarea cerintei a doua se face simplu in $O(1)$ modificand direct <tex> value[\ ] </tex>.
h3(#solutie-log-sqrt). Solutie $O(M*log(N)*sqrt(N))$
Aceasta solutie foloseste asa numita tehnica $longest path decomposition$, tehnica ce necesita cunostine minime despre grafuri si cu care vom obtine complexitatea $O(M*sqrt(N)*log(N))$ urmand pasii de mai jos:
# Elimina cel mai lung lant radacina-frunza din arbore si apeleaza recursiv pentru restul componentelor conexe;
# Retine fiecare lant ca un vector <tex> Path[].array[] </tex> cu noduri ordonate crescator dupa adancime si pastreaza un pointer catre nodul din lantul sau parinte <tex> Path[].parent </tex>;
# Pentru fiecare nod retine lantul caruia apartine <tex> whatPath[] </tex> si pozitia in vectorul lantului <tex> whatPos[] </tex>.
# Retine fiecare lant ca un vector <tex> Path[\ ].array[\ ] </tex> cu noduri ordonate crescator dupa adancime si pastreaza un pointer catre nodul din lantul sau parinte <tex> Path[\ ].parent </tex>;
# Pentru fiecare nod retine lantul caruia apartine <tex> whatPath[\ ] </tex> si pozitia in vectorul lantului <tex> whatPos[\ ] </tex>.
Este evident ca memoria ocupata este $O(N)$, fiecare nod fiind inclus intr-un singur lant. Numarul maxim de lanturi prin care putem trece pornind din radacina pana intr-una din frunze, este $O(sqrt(N))$.
