h1. Arbori Indexati Binar
 
(Categoria _Structuri de date_, autor _Giurgea Mihnea_)
 
 
h2. 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':http://infoarena.ro/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.
 
h2. 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
 
 
 

Scrie aici despre aib