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^2N), este urmatoarea: cautam binar pozitia, si la fiecare pas, pentru a compara pozitia curenta _i_ cu solutia, calculam in O(logN) suma elementelor de pe pozitiile 1...i, de unde si complexitatea finala de O(log^2N).
 
 
Tema pentru cititor: gasiti 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.