Preskoči na glavni sadržaj

Fenwickovo stablo

Uvod

Fenwickovo stablo je struktura podataka koja omogućuje upite sumom prefiksa niza i promjenu vrijednosti elementa niza, sve u O(log(n))O(log(n)). Fenwickovo stablo je još poznato pod imenom binarno indeksirano stablo, iako zapravo nije ni stablo, već niz.
Prije nego što objasnimo strukturu, upoznajmo se sa sljedećom operacijom.

Izoliranje posljednjeg postavljenog bita

Kao što naslov kaže, potrebno je iz nekog broja uzeti posljednji postavljeni bit, dakle bit čija je vrijednost 1.
Npr, imamo broj 14. Ako ga prikažemo u bazi 2, on izgleda ovako: 0000 1110
Ako izoliramo posljednji postavljeni bit, dobijemo 2 (0000 0010), a to se postiže bitovnom operacijom AND(&)AND(\&) s dvojnim komplementom broja. Brzo rješenje je sljedeće:

n&(n)n\&(-n)

Ova operacija je vrlo bitna za Fenwickovo stablo.

Struktura

Svaki indeks ii u Fenwickovom stablu predstavlja sumu intervala [i2j1+1,i][i - 2^{\smash{j - 1}} + 1, i], gdje jj predstavlja posljednji postavljeni bit u indeksu ii. Koristit ćemo 1-indeksiranje kod nizova.

Primjer:
Neka je L=i2j1+1L = i - 2^{\smash{j - 1}} + 1 početak intervala, a R=iR = i kraj intervala.

Indeks iibitovni prikazj=i&(i)j = i\&(-i)LLinterval [L,R][L, R]
100011120+11 - 2^{\smash{0}} + 1[1,1][1, 1]
200102221+12 - 2^{\smash{1}} + 1[1,2][1, 2]
300111320+13 - 2^{\smash{0}} + 1[3,3][3, 3]
401003422+14 - 2^{\smash{2}} + 1[1,4][1, 4]
501011520+15 - 2^{\smash{0}} + 1[5,5][5, 5]
601102621+16 - 2^{\smash{1}} + 1[5,6][5, 6]
701111720+17 - 2^{\smash{0}} + 1[7,7][7, 7]
810004823+18 - 2^{\smash{3}} + 1[1,8][1, 8]

Kako sad iz ovoga izračunati sumu prefiksa niza?
Uzet ćemo indeks 7 kao primjer. On predstavlja sumu intervala [7,7][7, 7]. Ako od njega oduzmemo posljednji postavljeni bit (1), dobijemo indeks 6, tj. interval [5,6][5, 6]. Od broja 6 oduzmemo njemu posljednji postavljeni bit (2). Dobijemo indeks 4 ili interval [1,4][1, 4].
Imamo sljedeće intervale: [1,4][1, 4], [5,6][5, 6], [7,7][7, 7]. Njihovom unijom dobijemo interval [1,7][1, 7] što predstavlja sumu prefiksa niza za indeks 7.

Ilustracija:
Fenwick tree - primjer

Programski kod za računanje sume prefiksa koristeći Fenwickovo stablo:

// suma intervala [1, index]
int prefixSum(int index, vector <int> &fenwickTree) {
int sum = 0;

while(index >= 1) {
sum += fenwickTree[index];

index -= index & -index;
}

return sum;
}

Promjena vrijednosti elementa niza

Dodavanje nekog broja xx elementu originalnog niza se vrši na sličan način kao i računanje sume prefiksa, samo ovaj put se kreće od manjeg indeksa prema većima. Kao primjer ćemo uzeti broj na indeksu 3, a cilj nam je promijeniti vrijednost za xx svim elementima Fenwickovog stabla koji prestavljaju sumu u kojoj se nalazi element na indeksu 3. Idemo obrnutim smjerom nego prije.

Prvo ažuriramo Fenwickovo stablo na indeksu 3: fenwickTree[3]+=xfenwickTree[3] += x
Zatim indeksu dodajemo posljednji postavljeni bit (1) i dobijemo 4.
Mijenjamo vrijednost Fenwickovog stabla na indeksu 4: fenwickTree[4]+=xfenwickTree[4] += x
Novi index: 8
fenwickTree[8]+=xfenwickTree[8] += x
...
postupak se nastavlja dok indeks ne prijeđe granice niza.

Fenwick tree - primjer

Programski kod je vrlo sličan onomu za dohvaćanje sume prefiksa:

//elementu na poziciji index dodaje x
void update(int index, int x, vector <int> &fenwickTree) {
while(index < fenwickTree.size()) {
fenwickTree[index] += x;

index += index & -index;
}
}
Oprez

U ovoj implementaciji fenwickTree.size()fenwickTree.size() ne označava pravu veličinu niza.
Ona je zapravo za 1 manja zbog nultog indeksa kojeg tu ne koristimo.

Koristeći ovu funkciju možemo iz bilo kojeg niza izgraditi Fenwickovo stablo:

/*
vraća Fenwickovo stablo za dani niz arr.
pretpostavimo da se radi o 1-indeksiranju
*/
vector <int> getFenwick(vector <int> arr) {
vector <int> fenwickTree(arr.size(), 0);

for(int i = 1; i < arr.size(); ++i) {
update(i, arr[i], fenwickTree);
}

return fenwickTree;
}

Sada efikasno možemo odgovoriti na upite o sumi nekog podniza od ll do rr na isti način kao kod niza suma prefiksa:

rangeSum(l,r)=prefixSum(r)prefixSum(l1)rangeSum(l, r) = prefixSum(r) - prefixSum(l - 1)
Informacija

Korištenje 1-indeksiranja nam pokriva rubni slučaj kad se pozove prefixSumprefixSum za indeks 0.

Ovime smo pokrili promjene nad jednim elementom i upite nad intervalima. Pogledajmo sada kako obavljati promjene nad intervalima i upite nad jednim elementom.

Range update, point query

Kako bi ovo postigli, potrebno je podsjetiti se difference arraya.
Kako bi intervalu [l,r][l, r] promijenili vrijednost za xx, potrebno je elementu na indeksu ll dodati xx, a onom na indeksu r+1r + 1 oduzeti.

Dohvaćanje vrijednosti je također isto kao kod niza razlika, potrebno je napraviti sumu prefiksa. Prednost je u tome što se dohvaćanje elementa koristeći Fenwickovo stablo obavlja u O(log(n))O(log(n)).

Programski kodovi

void rangeUpdate(int l, int r, int x, vector <int> &fenwickTree) {
update(l, x, fenwickTree);
update(r + 1, -x, fenwickTree);

/*
nije potrebno provjeravati je li r + 1 izvan granica
jer while(index < fenwickTree.size()) rješava taj slucaj
*/
}
// vraca vrijednost elementa na indeksu i
void pointQuery(int i, vector <int> &fenwickTree) {
return prefixSum(i, fenwickTree);
}