Fenvikova drveta (BIT)

U nastavku ćemo razmotriti još jednu strukturu podataka koja omogućava efikasno računanje statistika nad segmentima niza i ažuriranje pojedinačnih elemenata: to su Fenvikova drveta (engl. Fenwick tree), tj. binarno indeksirana drveta (engl. binary indexed tree, BIT) koja se malo jednostavnije implementiraju od segmentnih drveta, koriste malo manje memorije i mogu da budu za konstantni faktor brža od njih (iako je složenost operacija asimptotski jednaka). S druge strane, za razliku od segmentnih drveta, koja su pogodna za različite operacije, Fenvikova drveta su specijalizovana samo za asocijativne operacije koje imaju odgovarajuće inverzne (suprotne) operacije (npr. zbir ili proizvod elemenata segmenata se može nalaziti uz pomoć Fenvikovih drveta, jer sabiranju odgovara oduzimanje, a množenju deljenje, ali ne i minimum, najveći zajednički delilac i slično). Potrebu da za razmatranu operaciju postoji inverzna operacija ćemo detaljnije diskutovati kada budemo govorili o realizaciji samih operacija. Segmentna drveta mogu da urade sve što i Fenvikova, dok obratno ne važi.

Slično kao što je slučaj kod segmentnih drveta, iako se naziva drvetom, Fenvikovo drvo zapravo predstavlja niz vrednosti zbirova nekih pametno izabranih segmenata originalnog niza \(a\). Izbor segmenata je u tesnoj vezi sa binarnom reprezentacijom indeksa. Ključna Fenvikova ideja je sledeća:

Kao što se svaki prirodan broj može dobiti sabiranjem nekih stepena dvojke koji su određeni njegovom binarnom reprezentacijom (svaka jedinica i njen položaj u binarnoj reprezentaciji određuje neki stepen dvojke), tako se i svaki prefiks niza može dobiti nadovezivanjem nekih segmenata koji su određeni binarnom reprezentacijom granice tog segmenta (svaka jedinica i njen položaj u binarnoj reprezentaciji određuje jedan takav segment).

Ponovo ćemo, jednostavnosti radi, pretpostaviti da se vrednosti smeštaju od pozicije \(1\) (vrednost na poziciji \(0\) je irelevantna) i to i u polaznom nizu \(a\), i u nizu u kom se smešta Fenvikovo drvo. Prilagođavanje koda situaciji u kojoj su u polaznom nizu elementi smešteni od pozicije nula veoma je jednostavno, samo je na početku svake funkcije koja radi sa drvetom indeks polaznog niza potrebno uvećati za jedan pre dalje obrade. Dakle, ako je polazni niz dužine \(n\), elementi drveta se smeštaju u poseban niz na pozicije \([1, n]\).

Definicija Fenvikovog drveta je sledeća:

U drvetu se na poziciji \(k\) čuva zbir vrednosti polaznog niza sa pozicija iz intervala \((f(k), k]\), gde je \(f(k)\) broj koji se dobija od broja \(k\) tako što se u binarnom zapisu broja \(k\) prva jedinica zdesna zameni nulom.

Na slici 1 je za niz dužine \(16\) prikazano koji se zbirovi segmenata polaznog niza čuvaju na svakoj od pozicija u Fenvikovom drvetu. Primetimo da neparne pozicije odgovaraju segmentima dužine 1, a da za stepene broja 2 segmenti predstavljaju prefikse polaznog niza do te pozicije.

Na slici 2 prikazana je zavisnost zbirova segmenata od njihovih podsegmenata, odakle se jasno vidi da je zaista u pitanju drvolika struktura (otuda i potiče naziv Fenvikovo drvo). U listovima ove strukture nalaze se elementi polaznog niza, dok se u unutrašnjim čvorovima nalaze elementi Fenvikovog drveta.

Implementacija raznih operacija nad Fenvikovim drvetom je veoma jednostavna, ako se zna način da se iz binarnog zapisa broja ukloni prva jedinica zdesna tj. da se za dati broj \(k\) izračuna vrednost \(f(k)\). Označimo sa \(b(k)\) binarni broj koji sadrži samo jednu jedinicu i to na mestu poslednje jedinice u binarnom zapisu broja \(k\). Važi da je \(f(k) = k - b(k)\).

Pod pretpostavkom da su brojevi zapisani u potpunom komplementu, vrednost \(b(k)\) se može izračunati izrazom k & -k. Oduzimanjem te vrednosti od broja \(k\) tj. izrazom k - (k & -k) dobijamo efekat brisanja poslednje jedinice u binarnom zapisu broja \(k\) i to predstavlja implementaciju funkcije \(f\).

Dokažimo ispravnost operacije uklanjanje poslednje jedinice iz binarnog zapisa broja.

Drugi način da se izračuna vrednost \(f(k)\) jeste računanjem vrednosti izraza k & (k-1). Ispravnost ovog izraza se takođe može jednostavno dokazati. Naime, broj k-1 ima sve iste bitove od krajnjeg levog do pozicije poslednjog postavljenog bita u broju \(k\), a sve invertovane bitove posle krajnjeg desnog postavljenog bita u broju \(k\).

Ipak, izraz k - (k & -k) se češće koristi, zbog sličnosti sa izrazom k + (k & -k), koji se koristi prilikom izračunavanja funkcije \(g\) koja je definisana u poglavlju 1.4.2.2.2 posvećenom ažuriranju vrednosti elemenata niza.

Računanje zbira elemenata segmenta

Zbir elemenata u bilo kom prefiksu polaznog niza može da se dobije kao zbir nekoliko elemenata zapisanih u Fenvikovom drvetu.

Ove intervale je jednostavno odrediti. Na poziciji \(k\) se nalazi zbir elemenata sa pozicija iz intervala \((f(k), k]\), na poziciji \(f(k)\) zbir elemenata sa pozicija iz intervala \((f(f(k)), f(k)]\), itd. Postupak se nastavlja sabirajući elemente sa pozicija \(k\), \(f(k)\), \(f(f(k))\), \(f(f(f(k)))\) itd., sve dok se ne dođe do pozicije nula.

Broj elemenata Fenvikovog drveta čijim se sabiranjem dobija zbir prefiksa polaznog niza je \(O(\log{n})\). Naime, u svakom koraku se broj jedinica u binarnom zapisu tekućeg indeksa smanjuje, a broj \(n\) se binarno zapisuje sa najviše \(O(\log{n})\) binarnih jedinica.

Zbir elemenata prefiksa na pozicijama iz intervala \((0, k]\) polaznog niza \(a\) smeštenog u Fenvikovo drvo drvo možemo onda izračunati narednom funkcijom.

// na osnovu Fenvikovog drveta smeštenog u niz drvo
// izračunava zbir prefiksa (0, k] polaznog niza
int zbirPrefiksa(const vector<int>& drvo, int k) {
  int zbir = 0;
  while (k > 0) {
     zbir += drvo[k];
     k -= k & -k; // k = f(k)
  }
}

Kada umemo da izračunamo zbirove prefiksa polaznog niza, zbir proizvoljnog segmenta određenog pozicijama \([a, b]\) polaznog niza možemo izračunati kao razliku zbira prefiksa određenog pozicijama \((0, b]\) i zbira prefiksa određenog pozicijama \((0, a-1]\). Pošto se oba prefiksa računaju u vremenu \(O(\log{n})\), i zbir svakog segmenta možemo izračunati u vremenu \(O(\log{n})\). Istaknimo na ovom mestu da je zbog ove operacije važno da asocijativna operacija koja se koristi u Fenvikovom drvetu ima inverznu operaciju (u ovom slučaju, pošto se radi o operaciji sabiranja, da bismo mogli da oduzimanjem dve vrednosti prefiksa dobijemo zbir proizvoljnog segmenta¹).

Ažuriranje vrednosti elementa

Ideju računanja zbira elemenata proizvoljnog segmenta kao razlike dva zbira prefiksa smo videli već ranije, kada smo u te svrhe održavali niz svih zbirova prefiksa. Osnovna prednost Fenvikovih drveta u odnosu na niz svih zbirova prefiksa je to što se mogu efikasno ažurirati. Naime, ažuriranje jednog elementa polaznog niza može rezultovati izmenom vrednosti velikog broja prefiksnih zbirova, naročito ako je element koji menjamo blizu početka niza (u najgorem slučaju broj zbirova koje je potrebno ažurirati je \(O(n)\)). Stoga je operacija ažuriranja elementa kada se koriste prefiksni zbirovi u najgorem slučaju složenosti \(O(n)\).

Razmotrimo funkciju koja ažurira Fenvikovo drvo nakon uvećanja elementa u polaznom nizu na poziciji \(k\) za vrednost \(x\). Tada je za \(x\) potrebno uvećati sve one zbirove u drvetu u kojima se kao sabirak javlja i element na poziciji \(k\). Potrebno je ažurirati sve one pozicije \(m\) čiji pridruženi segment sadrži vrednost \(k\), tj. sve one pozicije \(m\) takve da je \(k \in (f(m), m]\), tj. pozicije \(m\) za koje važi

\[f(m) < k \leq m\](1)

Te pozicije se izračunavaju veoma jednostavno krenuvši od polazne pozicije \(k\), slično kao u prethodnoj funkciji, s tim što se umesto da se od broja \(k\) oduzima vrednost \(b(k)\), broj \(k\) uvećava za vrednost izraza \(b(k)\). Obeležimo sa \(g(k)\) broj \(k+b(k)\), koji se dobija od broja \(k\) tako što se \(k\) sabere sa brojem koji ima samo jednu jedinicu u svom binarnom zapisu i to na poziciji na kojoj se nalazi poslednja jedinica u binarnom zapisu broja \(k\). U implementaciji se broj \(g(k)\) lako može izračunati po formuli k + (k & -k).

Dokazaćemo da je potrebno i dovoljno ažurirati vrednosti na pozicijama \(k\), \(g(k)\), \(g(g(k))\) itd., sve dok se ne dođe do pozicije koja je strogo veća od dužine niza \(n\).

S obzirom na to da se broj \(n\) binarno zapisuje sa \(O(\log{n})\) bitova i da se u svakom koraku broj krajnjih nula u zapisu broja povećava (iako u svakom koraku vrednost broja raste), ukupan broj koraka je jednak \(O(\log n)\). Dakle, broj elemenata Fenvikovog drveta čije je vrednosti potrebno izmeniti iznosi \(O(\log n)\).

// ažurira Fenvikovo drvo smešteno u niz drvo nakon što se
// u originalnom nizu element na poziciji k uveća za x
void uvecaj(vector<int>& drvo, int n, int k, int x) {
  while (k <= n) {
    drvo[k] += x;
    k += k & -k;
  }
}

Dokažimo korektnost opisanog postupka. Krenimo od naredne leme.

Dokažimo i drugu pomoćnu lemu.

Dokažimo sada i glavno tvrđenje.

Prethodna teorema garantuje da su jedine pozicije koje treba ažurirati u drvetu prilikom ažuriranja elementa na poziciji \(k\) u polaznom nizu upravo pozicije iz serije \(k\), \(g(k)\), \(g(g(k))\), itd., sve dok su one manje ili jednake \(n\), pa su prethodni postupak i njegova implementacija korektni.

Formiranje Fenvikovog drveta

Ostaje još pitanje kako inicijalno formirati Fenvikovo drvo. Formiranje se može svesti na to da se kreira drvo popunjeno samo nulama, a da se zatim uvećava vrednost jednog po jednog elementa niza prethodnom funkcijom.

// na osnovu niza a u kom su elementi smešteni
// na pozicijama iz segmenta [1, n] formira Fenvikovo drvo
// i smešta ga u niz drvo (na pozicije iz segmenta [1, n])
vector<int> formirajDrvo(int n, const vector<int>& a) {
  vector<int> drvo(n+1);
  fill_n(drvo + 1, n, 0);
  for (int k = 1; k <= n; k++)
     uvecaj(drvo, n, k, a[k]);
  return drvo;
}

Primer 1.4.16. Razmotrimo problem formiranja Fenvikovog drveta za niz vrednosti \(3, 1, 9, 4, 6, 6, 2, 7\). Krenuvši od niza koji sadrži samo nule, uvećavamo jedan po jedan element niza.

Ova implementacija \(n\) puta poziva funkciju uvecaj koja je složenosti \(O(\log n)\), te je ukupna složenost ovog algoritma \(O(n\log n)\). Međutim, pokazuje se da možemo i bolje od ovog. Naime, svaki element Fenvikovog drveta sadrži zbir elemenata nekog segmenta polaznog niza, pa za izračunavanje elemenata Fenvikovog drveta možemo iskoristiti zbirove prefiksa. Naime, element na poziciji \(k\) u Fenvikovom drvetu dobijamo kao razliku zbira prefiksa \((0,k]\) i zbira prefiksa \((0,f(k)]\), ako je \(f(k)>0\), dok ako je \(f(k)=0\) element na poziciji \(k\) biće jednak baš zbiru prefiksa \((0,k]\).

vector<int> formirajDrvoPrefiksneSume(int n, const vector<int>& a) {
  vector<int> drvo(n+1);
  vector<int> sume_prefiksa(n+1,0);
  sume_prefiksa[1] = a[1];
  for (int k = 2; k <= n; k++)
    sume_prefiksa[k] = sume_prefiksa[k-1] + a[k];
  
  fill_n(drvo + 1, n, 0);
  for (int k = 1; k <= n; k++) {
    // racunamo f(k)
    int f_k = k - (k & -k);
    // od sume prefiksa do k oduzimamo sumu prefiksa do f(k)
    // ako je f(k)=0, onda ne vrsimo oduzimanje
    drvo[k] = sume_prefiksa[k] - (f_k > 0 ? sume_prefiksa[f_k] : 0);
  }
  return drvo;
}

Izračunavanje zbirova svih prefiksa polaznog niza je vremenske složenosti \(O(n)\), ali se nakon toga elementi Fenvikovog drveta računaju u vremenu \(O(1)\), te je ukupna vremenska složenost ovog pristupa \(O(n)\). Ova implementacija pak zahteva dodatni memorijski prostor veličine \(O(n)\) za smeštanje prefiksnih zbirova.

Primetimo da su za izračunavanje \(k\)-tog elementa Fenvikovog drveta potrebni samo elementi niza prefiksnih zbirova na pozicijama \(j\leq k\). Ovo opažanje omogućava da koristimo samo jedan niz koji ćemo inicijalizovati na niz prefiksnih zbirova, a zatim počev od poslednjeg elementa niza idući ka prvom elementu menjati element po element sa prefiksnog zbira na element Fenvikovog drveta.

vector<int> formirajDrvoPrefiksneSumeOpt(int n, const vector<int>& a) {
  vector<int> drvo(n+1);
  fill_n(drvo+1, n, 0);

  drvo[1] = a[1];
  for (int k = 2; k <= n; k++)
    drvo[k] = drvo[k-1] + a[k];
  
  for (int k = n; k >= 1; k--){
    int f_k = k - (k & -k);
    if (f_k > 0) drvo[k] -= drvo[f_k];
  }
  return drvo;
}

Ova implementacija algoritma za formiranje Fenvikovog drveta je vremenske složenosti \(O(n)\), a dodatne prostorne složenosti \(O(1)\).