h3. (problema medie clasele XI-XII)

O prima idee de rezolvare a problemei are o complexitate de $O(1)$ la operatiile de tip update si $O(n)$ la operatiile de tip query. Cand intalnim o operatie de tip 1 este necesar sa folosim un vector $S[1..N]$ in care marcam aceste modificari. Astfel, adunand valoarea $s$ la elementul $S[p]$ vom observa ca suma pe care a primit-o un nod $X$ este de fapt suma valorilor $S[nod]$ unde $nod$ reprezinta indicele nodurilor din drumul lui $X$ pana la radacina arborelui. Deci, pentru o operatie de tipul 1 vom face o singura adunare, iar pentru o operatie de tipul 2 vom efectua o parcurgere in adancime pentru a cauta suma ceruta. Aceasta solutie obtine in jur de $30$ de puncte.

O prima idee de rezolvare a problemei are o complexitate de O(1) la operatiile de tip update si O(n) la operatiile de tip query. Cand intalnim o operatie de tip 1 este necesar sa folosim un vector S[1..N] in care marcam aceste modificari. Astfel, adunand valoarea s la elementul S[p] vom observa ca suma pe care a primit-o un nod X este de fapt suma valorilor S[nod] unde nod reprezinta indicele nodurilor din drumul lui X pana la radacina arborelui. Deci, pentru o operatie de tipul 1 vom face o singura adunare, iar pentru o operatie de tipul 2 vom efectua o parcurgere in adancime pentru a cauta suma ceruta. Aceasta solutie obtine in jur de 30 de puncte.

O alta abordare ar fi reducerea problemei la nivel de vector. Am putea renumerota nodurile arborelui astfel incat subarborele fiecarui nod sa aiba id-uri consecutive. Acest lucru se poate face cu o parcurgere in adancime. Acum trebuie sa efectuam adunari pe intervale compacte de pe un vector, si trebuie sa gasim un element din vector ce are o anumita suma. Acest lucru se poate face, de asemenea in $O(1)$ pentru update si $O(N)$ pentru query usor. Aceasta solutie este mai rapida decat prima, deoarece nu foloseste apeluri recursive ale functiilor si efectueaza un numar mic de operatii. Asa s-ar fi luat $50-60$ de puncte In cazul in care problema s-ar fi redus la nivel de vector dar atat update-ul cat si querry-ul s-ar fi efectuat in $O(n)$ s-ar fi obtinut $30-40$ de puncte..

O alta abordare ar fi reducerea problemei la nivel de vector. Am putea renumerota nodurile arborelui astfel incat subarborele fiecarui nod sa aiba id-uri consecutive. Acest lucru se poate face cu o parcurgere in adancime. Acum trebuie sa efectuam adunari pe intervale compacte de pe un vector, si trebuie sa gasim un element din vector ce are o anumita suma. Acest lucru se poate face, de asemenea in O(1) pentru update si O(N) pentru query usor. Aceasta solutie este mai rapida decat prima, deoarece nu foloseste apeluri recursive ale functiilor si efectueaza un numar mic de operatii. Asa s-ar fi luat 50-60 de puncte In cazul in care problema s-ar fi redus la nivel de vector dar atat update-ul cat si querry-ul s-ar fi efectuat in O(n) s-ar fi obtinut 30-40 de puncte..

Solutia care ar fi obtinut punctajul maxim se bazeaza pe reducerea problemei la nivel de vector, descrisa in paragraful precedent. Fie {$SEC = sqrt(N)$}. Putem imparti vectorul de lungime $N$ in $SEC$ secvente de lungime {$SEC$}. Vom mai folosi 3 vectori $A[1..N]$ reprezentand sumele pe fiecare element ce au fost adunate la inceputul secventelor de lungime {$SEC$}, $C[1..SEC]$ reprezinta sumele ce s-au adunat pe intregile secvente, iar $P[1..SEC][1..1 000 000]$ este o matrice binara unde $P[i][j] = 1$ daca exista un element din secventa $i$ astfel incat {$A[element] = j$}. Aceasta idee ne ajuta sa rezolvam problema intr-o complexitate de $O(sqrt(n))$ atat pentru query cat si pentru update. Pentru ca memoria folosita sa fie rezonabila implementarea matricii $P$ se face pe biti.

Solutia care ar fi obtinut punctajul maxim se bazeaza pe reducerea problemei la nivel de vector, descrisa in paragraful precedent. Fie SEC = sqrt(N). Putem imparti vectorul de lungime N in SEC secvente de lungime SEC. Vom mai folosi 3 vectori A[1..N] reprezentand sumele pe fiecare element ce au fost adunate la inceputul secventelor de lungime SEC, C[1..SEC] reprezinta sumele ce s-au adunat pe intregile secvente, iar P[1..SEC][1..1 000 000] este o matrice binara unde P[i][j] = 1 daca exista un element din secventa i astfel incat A[element] = j. Aceasta idee ne ajuta sa rezolvam problema intr-o complexitate de O(sqrt(n)) atat pentru query cat si pentru update. Pentru ca memoria folosita sa fie rezonabila implementarea matricii P se face pe biti.

h2. Pedefe
(problema grea clasele XI-XII)

1. http://infoarena.devnet.ro/forum/index.php/topic,935.0.html
2. http://infoarena.devnet.ro/forum/index.php/topic,999.0.html