Arbori indexați binar

Avem un sir de numere si se pun intrebari de forma:

Cat este suma elementelor cu indicii intre a si b? (QUERY)

Modifica valoarea unui element. (UPDATE)

Fie n = 100.000 numarul de elemente din sir

q = 100.000 numarul de intrebari (de tip QUERY sau UPDATE)

Iar V sirul de numere.

BRUT

void update(int pos, int val) {

V[pos] = val;

}

int query(int pos) {

int sum = 0;

for (int i = 1; i <= pos; ++i) {

sum += V[i];

}

return sum;

}

Functia update este o(1), dar query este o(n), fiind cam inceata.

OPTIM

Folosim sume partiale.

QUERY:

int query(int pos) {

return S[pos];

}

UPDATE:

void update(int pos, int val) {

int currentVal = S[pos] - S[pos - 1];

for (int i = pos; i <= N; ++i) {

S[i] += val - currentVal;

}

}

In acest caz, query se executa in o(1) dar update in o(n).

Cu AIB obtin o( log2n) si pe UPDATE si pe QUERY.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

Mai sus avem reprezentarea grafica a AIB-ului pentru urmatoru sir:

V: 2 6 1 8 7 0 4 5 6 9 7 2 1 0 0 0

Din fiecare nod merg in stanga cat pot.

Aceste valori de sus le voi tine chiar in nodul frunza corespunzator.

A[4] = V[1] + V[2] + V[3] + V[4]

A[5] = V[5]

A[6] = V[5] + V[6]

A[7] = V[7]

A[8] = V[1] + V[2] + + V[8]

Observam ca fiecare element din A este suma unei secvente din V de lungime putere de 2 terminata la indicele din V, egal cu pozitia ceruta din A.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

1 10 11 100 101 110 111 1000 1001 1010 1011 1100 1101 1110 1111 10000

2 6 1 8 7 0 4 5 6 9 7 2 1 0 0 0

= Indicii in baza 10 = indicii in baza 2 = valori sirul initial

La fiecare indice se tine suma dintr-o secventa de lungime putere de 2 terminata la acea pozitie, unde exponentul puterii lui 2 este chiar numarul de 0-ur de la finalul scrierii in baza 2 a indicelui.

Deci, ca sa calculez suma din sirul dat de la pozitia 1 la pozitia i, voi scrie pe i ca suma de puteri de 2. ( pentru i = 12 avem i = 22 + 23 )

i = 1210 = 11002, are la final 2 de 0 => A[12] memoreaza o secventa de lungime 22 = 4, terminata la pozitia 12. Scad 4 din 12 si ajung la A[8] care are suma tuturor elementelor de la 1 la 8 ( pentru ca 810=10002 , are trei 0-uri la final, adica memoreaza suma unei secvente de lungime

23 = 8, adica toate).