Fenvik stablo

Fenvik stablo ili binarno indeksno stablo je struktura podataka koja nam omogućava efikasno izračunavanje i manipulaciju prefiksnih suma sa vec izračunatim vrednostima koji ova struktura nudi. Ovu strukturu je predlozio Piter Fenwick 1994. godine ^[1] Fenvik Stablo prvenstveno rešava problem prefiksne sume i modifikacije elemenata u vrlo efikasnom vremenu. Postoji mogućnost da sami izračunamo tablu prefiksnu sume gde bi kompleksnost tok izračunavanja bila $O(n)$ a čitanje iz tabele $O(1)$ ,ali problem nastaje kada se od nas zahteva da modifikujemo neki element u tabeli. Fenvik stablo računa prefiksne sume i modifikaciju tabele u $O(\log n)$ vremenu, gde je $n$ veličina tabele.

Opis

Ako vam je zadat neki niz vrednosti, ponekad je neophodno izračunati ukupnu sumu tih vrednosti od nekog indeksa do drugog asocijativno. Fenvikno stablo omogućava metodu podelе ukupnih vrednosti svakog indeksa, kao i izmenu tih vrednosti nakon neke veće promene u nizu koje bi uticali na odgovarajuću vrednost. U praksi ova struktura je implementirana korišćenjem niza analognim implementaciji Binarnog hipa. Svaki indeks u nizu predstavlja neki čvor, indeks nekog od ćvorova roditelja ili deteta se računa preko bitwise operacija nad binarnom sistemu. Svaki indeks sadrži već izračunatu sumu iz nekog dela tabele, kombinacijom te sume kao i sa vrednostima čvorova tokom prolaženja do korena stabla, prefiksna suma biva izračunata. Kad se promeni neka vrednost u nizu, svi delovi sume koji sadrže modifikovanu vrednost su izmenjena sličnim prolazom kroz drvo. Sve modifikacije stabla su izvršene u asimptotskom vremenu jednakom - $O(\log n)$ u najgorem slučaju.

Proces izgradnje Fenvik stabla preko već nekog niza se izvršava u $O(n\log n)$ vremenu. Druge efikasne metode uključuju lociranje indeksa vrednosti ako su sve vrednosti pozitivne, ili ako su sve vrednosti negativne. Takođe postoji mogućnost izračunavanja sume nekog pod niza, a rešenje toga je oduzimanje prefiksne sume do desnog kraja trazenog indeksa sa prefiksnom sumom levog indeksa - 1 .

Aplikacije

Fenvik stablo je korišćeno da implementira aritmetičko kodiran algoritam.

Korišćenjem ovog stabla veoma lako je izgenerisati kumulativne sume neke liste. Iz kumulativne tabele je moguće izračunati zbir frekvencija u odredjenom segmentu u $O(\log n)$ kompleksnosti.

Fenvik stablo se takodje može koristiti za izračunavanje sume i dodele novim vrednostima multi dimenzionalnim nizovima gde je kompleksnost ovakvih operacija $O(2^{d}\log ^{d}n)$ , d je broj dimenzija a n je broj elemenata duž svake dimenzije. ^[2]

Implementacija

Ovo je primer programa koji implementira binarno indeksno stablo napisano u programskom jeziku C.

#include<stdio.h>
#include<stdlib.h>
#define N 5 //definisemo velicinu niza
int niz_unosa[N]; //definisemo niz

void izmeni_stablo(int *stablo,int indeks,int vrednost){ 
	while(indeks<=N){
		stablo[indeks]+=vrednost;
		indeks+=indeks&(-indeks); //formula za prolazenje kroz BIT kada izmenjujemo vrednosti
	}
	
}
int *napravi_stablo(){
	int *stablo = (int*)malloc(sizeof(N*sizeof(int))); //deklarisemo dinamcki niz koji ce predstavljati BIT
	for(int i=0;i<=N;i++){
		stablo[i]=0; //deklarisemo sve vrednosti na 0
	}
	for(int i=0;i<N;i++){
		izmeni_stablo(stablo,i+1,niz_unosa[i]); //koriscenjem funkcije koja izmenjuje stablo mi pravimo stablo,kompleksnost O(N*LOGn)
	}
	return stablo; // vracamo novo-kreirano stablo
}
int stampaj_sumu(int *stablo,int indeks){
	int s=0;
	while(indeks){
		s+=stablo[indeks];
		indeks-=indeks&(-indeks); //formula za prolazenje kroz BIT kada stampamo sumu
	}
	return s;
}
int main(){
	niz_unosa[0]=5;
	niz_unosa[1]=15;
	niz_unosa[2]=3;
	niz_unosa[3]=9;
	niz_unosa[4]=42;

	int *stablo = napravi_stablo();
	printf("%d ",stampaj_sumu(stablo,3)); // stampamo sumu prva 3 elementa. REZULTAT = 23
	printf("%d",stampaj_sumu(stablo,5) - stampaj_sumu(stablo,3)); //stampamo sumu pod niza gde je levi kraj na indeksu 4 a desni na indeksu 5 . REZULTAT = 51

}

Vidi još

Reference

^ Peter M. Fenwick (1994). „A new data structure for cumulative frequency tables”. Software: Practice and Experience. 24 (3): 327—336. doi:10.1002/spe.4380240306.
^ Pushkar Mishra (2013). „A New Algorithm for Updating and Querying Sub-arrays of Multidimensional Arrays”.

Spoljašnjе veze

[1] Peter M. Fenwick (1994). „A new data structure for cumulative frequency tables”. Software: Practice and Experience. 24 (3): 327—336. doi:10.1002/spe.4380240306.

[2] Pushkar Mishra (2013). „A New Algorithm for Updating and Querying Sub-arrays of Multidimensional Arrays”.

[1]

[2]