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

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 care cere cam asta.
Feedback(Silviu): link 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.

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.

Feedback(Silviu): AIB-urile sunt chiar mai rapide decat arborii de intervale (au constanta mai mica). Merita mentionat :P

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