AIB

[cristi8]

2 intrebari am si eu despre AIB:

1) daca am un arbore indexat binar de maxim, si vreau sa micsorez o valoare din sir, cum fac update ? (risc sa micsorez elementul maxim)

2) stiu ca a mai fost discutat pe forum, dar am uitat unde..: cum calculez in O(1) 2^(numarul de zerouri terminale) a unui nr ?

[•domino]

1) Cu un aib de maxim poti face:
QUERY(i): MAX ( A[1] , A[2] ... A)
UPDATE(i,j): A = MAX(A, j)
Nu cred k poti micsora prea usor.. foloseste arbori de intervale.

2) ((x) & (x-1)) ^ (x) (asta da defapt 2^Z, unde Z e nr de zero-uri)