Revizia anterioară Revizia următoare
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.
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.
Indicele x | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
Inceputul subsecventei asociata lui AIB[x] | 1 | 1 | 3 | 1 | 5 | 5 | 7 | 1 | 9 | 9 | 11 | 9 | 13 | 13 | 15 | 1 |
To do:
+cum calc. 2^k
+implementare operatii
+complexitate timp+spatiu
+bi-dimensional
+ce altceva mai face?
+ex. probleme