|
Titlul: AIB Scris de: cristi8 din Februarie 28, 2006, 22:02:23 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 ? Titlul: AIB Scris de: Mircea Pasoi din Februarie 28, 2006, 22:25:34 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) |