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?
Pentru un exemplu mai concret, vezi problema 'datorii':http://infoarena.ro/problema/datorii.

Fie un vector de numere care se modifica in timp real. Ne propunem sa raspundem la query-uri de genul: "Cat este suma unei subsecventei?".

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':http://infoarena.ro/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.

*Feedback(Silviu)*: Un enunt ceva mai clar la problema n-ar strica. "Vector care se modifica in timp real" lasa multe semne de intrebare :) In plus, cred ca avem problema 'datorii':problema/datorii care cere cam asta.
*Feedback(Silviu)*: 'link':http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees de pe TC. E un punct de plecare ;)
 
*Feedback(Cosmin)*: de ce nu punem direct link la articolul de pe topcoder? Pare stupid sa reinventam roata.
*Raspuns(Silviu)*: Nu trebuie tratat foarte amplu subiectul AIB (niste explicatii pe scurt si apoi un link catre tutorialul de pe TC). Totusi, sectiunea de probleme care se rezolva cu AIB ar fi numai ea valoroasa in sine pentru ca tutorialele de pe TC dau probleme numai de pe TC :D. De fapt, asa as vrea sa tratam situatiile in care avem deja un material bun la o chestie: o introducere, niste explicatii pe scurt (eventual ce nu se acopera bine acolo) si apoi aplicatii/probleme.
 
*Feedback(Cosmin)*: De acord, ma gandeam ca ar fi util chiar daca nu contine prea mult material o pagina scurta cu cateva comentarii ce completeaza articolul, oricare ar fi asta. Si ii spuneam lui mircea ca ar fi misto sa folosim chestia de comentarii de la blog. Eventual deschisa by default.
 
Am putea sa implementam usor un algoritm naiv de complexitate O(N), sau cu ceva efort sa folosim 'arbori de intervale':http://infoarena.ro/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.
 
*Feedback(Silviu)*: AIB-urile sunt chiar mai rapide decat arborii de intervale (au constanta mai mica). Merita mentionat :P

h2. Concret - Cum?
Fie V vectorul de numere care se modifica in timp real. Vom reprezenta AIB-ul folosind un alt vector, pe care il vom denumi, sugestiv, AIB, cu urmatoarea semnificatie:

_AIB[x]_ = suma subsecventei din V cu capetele: _[x - 2^k^ + 1; x]_, unde k = numarul de 0-uri terminale din reprezentarea binara a lui x.

_AIB[x]_ = suma subsecventei din V cu capetele: _[x - 2 ^k^ + 1; x]_, unde k = numarul de 0-uri terminale din reprezentarea binara a lui x.

| Indicele _x_ |1|2|3|4|5|6|7|8|9|10|11|12|13|14|15|16|
| Inceputul subsecventei asociata lui _AIB[x]_ |1|1|3|1|5|5|7|1|9|9|11|9|13|13|15|1|
h2. Detalii implementare

Valoarea x - 2^k^ + 1, unde k = numarul de 0-uri terminale se poate calcula foarte usor astfel:
 
_#define zeros(x) ( (x ^ (x - 1)) & x )_
 
Aceast define va calcula valoarea 2^k^ pentru x, unde k = numarul de 0-uri terminale. Pentru a intelege de ce, sa luam cateva exemple:
 
| x | 10011000| 11001111|
| x-1 | 10010111| 11001110|
| x ^ (x-1) | 00001111| 00000001|
| (x ^ (x-1)) & x | 00001000 | 00000001|
 
Folosind acest define, implementarea operatiilor devine foarte simpla.
 
== code(c) |
void Add(int x, int quantity)
{
    int i;
 
    for (i = x; i <= N; i += zeros(i))
        AIB[i] += quantity;
}
 
int Compute(int x)
{
    int i, ret = 0;
 
    for (i = x; i > 0; i -= zeros(i))
        ret += AIB[i];
    return ret;
}
 
==
 
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)_.
 
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.
 
AIB-urile se pot extinde usor la cazul multidimensional, si lasam aceasta implementare ca tema pentru cititor.

Valoarea x - 2 ^k^ + 1, unde k = numarul de 0-uri terminale se poate calcula foarte usor astfel:

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.

#define zeros(x) ( (x ^ (x - 1)) & x )
Aceast define va calcula valoarea 2 ^k^ pentru x, unde k = numarul de 0-uri terminale. Pentru a intelege de ce, sa luam un exemplu:
| x | 10011000 |
| x-1 | 10010111 |
| b | 00001111 |
| a | 00001000 |
x ^ (x-1)
(x ^ (x-1)) & x
To do:
+cum calc. 2^k
+implementare operatii
+complexitate timp+spatiu
+bi-dimensional
+ce altceva mai face?
+ex. probleme