Arbori Indexati Binar

(Categoria Structuri de date, autor Giurgea Mihnea)

Abstract - Problema

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?".

Am putea sa implementam usor un algoritm naiv de complexitate O(N), sau cu ceva efort sa folosim 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.

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.

To do:
+cum calc. 2^k
+implementare operatii
+complexitate timp+spatiu
+bi-dimensional
+ce altceva mai face?
+ex. probleme