_TO ADD:_ ce alte probleme de pe infoarena se mai rezolva cu AIB-uri?
de asemenea, de ce nu merge urmatoarul textile cod? Mircea: Merge, trebuie un Enter dupa si fara spatii la inceput.
 
* 'Datorii':problema/datorii
* 'Ben':http:problema/ben
* 'Evantai':problema/evantai
 
Mircea: cum gasesti al K-lea numar intr-un AIB in O(lg^2^ N) si O(lg N) (aplicat: 'Schi':problema/schi) [cosmin: ai furat rapid jmenu cu log n ;), hmm acuma vad ca e si in tutorialul de pe topcoder desi nu cred sa il fi citit inainte, nu imi dau seama daca mi-am amintit jmenu de undeva sau m-am prins singur]
 

h1. Arbori Indexati Binar
(Categoria _Structuri de date_, autor _Giurgea Mihnea_)

h2. Abstract - Problema
AIB-urile sunt o structura de date care implementeaza eficient urmatoarea problema: avem un vector de numere, si vrem sa raspundem la urmatoarele operatii asupra lui:

1. se incremeneaza/ decrementeaza un numar din vector
2. care este suma unei anumite subsecvente a vectorului?

 
# se incremeneaza/ decrementeaza un numar din vector
# care este suma unei anumite subsecvente a vectorului?

Pentru un exemplu mai concret, vezi problema 'datorii':problema/datorii.
Sa ne gandim la cateva posibile solutii: am putea sa implementam usor un algoritm naiv de complexitate O(N), sau cu ceva efort sa folosim 'arborii de intervale':arbori-de-intervale pentru o complexitate O(logN). In continuare va vom prezenta structura de date numita AIB, usor de implementat si de aceeasi complexitate ca si arborii de intervale. Mai mult, deoarece acestia au constanta mult mai mica decat arborii de intervale, in practica se vor dovedi mult mai rapizi si vor ocupa si mai putina memorie.

==

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.

h2. Aplicatii
 
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 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.
 

AIB-urile se pot extinde usor la cazul multidimensional, si lasam aceasta implementare ca tema pentru cititor. De asemenea, incercati sa rezolvati urmatoarele probleme de pe infoarena:
1. 'Datorii':problema/datorii
2. 'Ben':problema/ben
3. 'Evantai':problema/evantai

4. 'Schi':problema/schi
 
 

Pentru o lectura mai profunda in acest domeniu, va recomand 'acest articol de pe TopCoder':http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees.