==

Functia Add(x, quantity) incrementeaza valoarea lui AIB[x] cu quantity, care poate fi si negativ pentru a decrementa. Functia Compute(x) calculeaza suma AIB [1] + AIB [2] + ... + AIB [x]. Pentru a calcula suma subsecventei AIB [L...U] folositi _Compute(U) - Compute(L-1)_.

Functia Add(x, quantity) incrementeaza valoarea lui V[x] cu quantity, care poate fi si negativ pentru a decrementa. Functia Compute(x) calculeaza suma V [1] + V [2] + ... + V [x]. Pentru a calcula suma subsecventei V [L...U] folositi _Compute(U) - Compute(L-1)_.

Complexitatea in timp a fiecarei operatii este O(logN), pentru ca, in cazul celei de-a doua operatii, la fiecare pas ultimul bit nenul al lui _i_ devine nul, si deci _for_-ul va itera de maxim log x ori. Structura ocupa spatiu O(N), doar vectorul AIB.

Sa presupunem ca problema initiala se restrange la a marca/ demarca o pozitie, si ne propunem sa aflam care este cea de a K-a pozitie marcata.

O prima idee de rezolvare, de complexitate O(log^2^ N), este urmatoarea: cautam binar pozitia, si la fiecare pas, pentru a compara pozitia curenta _i_ cu solutia, calculam in O(logN) functia _cnt(i) :=_ suma elementelor de pe pozitiile 1...i; _cnt(i)_ reprezinta de fapt numarul de numere intre 1 si i, pe care il comparam cu K pentru a stii cum facem urmatorul pas.

O prima idee de rezolvare, de complexitate O(log^2^ N), este urmatoarea: cautam binar pozitia, si la fiecare pas, pentru a compara pozitia curenta _i_ cu solutia, calculam in O(logN) functia _cnt(i) :=_ suma elementelor de pe pozitiile 1...i; _cnt(i)_ reprezinta de fapt numarul de numere intre 1 si i, pe care il comparam cu K pentru a sti cum facem urmatorul pas.

A doua idee de rezolvare, de complexitate O(logN) se poate realiza optimizand prima idee. Folosim 'cautarea binara a lui Patrascu':http://infoarena.ro/multe-smenuri-de-programare-in-cc-si-nu-numai si urmatoarea observatie: cnt(8+4) = cnt(8) + AIB[8+4], cnt(16+4) = cnt(16) + AIB[16+4], etc. Daca ne uitam la cum functioneaza functia Compute(int x), putem generaliza astfel: cnt(x) = cnt(x - zeros(x)) + AIB[x]. Implementarea propriu-zisa o lasam ca tema pentru cititor, impreuna cu problema gasirii celui de-al K-lea numar dintr-un AIB oarecare, pornind de la ideea de mai sus.