Фенвик стабло

Фенвик стабло или бинарно индексно стабло је структура података која нам омогућава ефикасно израчунавање и манипулацију префиксних сума са вец израчунатим вредностима који ова структура нуди. Ову структуру је предлозио Питер Фенwицк 1994. године ^[1] Фенвик Стабло првенствено решава проблем префиксне суме и модификације елемената у врло ефикасном времену. Постоји могућност да сами израчунамо таблу префиксну суме где би комплексност ток израчунавања била $O(n)$ а читање из табеле $O(1)$ ,али проблем настаје када се од нас захтева да модификујемо неки елемент у табели. Фенвик стабло рачуна префиксне суме и модификацију табеле у $O(\log n)$ времену, где је $n$ величина табеле.

Опис

Ако вам је задат неки низ вредности, понекад је неопходно израчунати укупну суму тих вредности од неког индекса до другог асоцијативно. Фенвикно стабло омогућава методу поделе укупних вредности сваког индекса, као и измену тих вредности након неке веће промене у низу које би утицали на одговарајућу вредност. У пракси ова структура је имплементирана коришћењем низа аналогним имплементацији Бинарног хипа. Сваки индекс у низу представља неки чвор, индекс неког од ћворова родитеља или детета се рачуна преко битwисе операција над бинарном систему. Сваки индекс садржи већ израчунату суму из неког дела табеле, комбинацијом те суме као и са вредностима чворова током пролажења до корена стабла, префиксна сума бива израчуната. Кад се промени нека вредност у низу, сви делови суме који садрже модификовану вредност су измењена сличним пролазом кроз дрво. Све модификације стабла су извршене у асимптотском времену једнаком - $O(\log n)$ у најгорем случају.

Процес изградње Фенвик стабла преко већ неког низа се извршава у $O(n\log n)$ времену. Друге ефикасне методе укључују лоцирање индекса вредности ако су све вредности позитивне, или ако су све вредности негативне. Такође постоји могућност израчунавања суме неког под низа, а решење тога је одузимање префиксне суме до десног краја тразеног индекса са префиксном сумом левог индекса - 1 .

Апликације

Фенвик стабло је коришћено да имплементира аритметичко кодиран алгоритам.

Коришћењем овог стабла веома лако је изгенерисати кумулативне суме неке листе. Из кумулативне табеле је могуће израчунати збир фреквенција у одредјеном сегменту у $O(\log n)$ комплексности.

Фенвик стабло се такодје може користити за израчунавање суме и доделе новим вредностима мулти димензионалним низовима где је комплексност оваквих операција $O(2^{d}\log ^{d}n)$ , д је број димензија а н је број елемената дуж сваке димензије. ^[2]

Имплементација

Ово је пример програма који имплементира бинарно индексно стабло написано у програмском језику 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

}

Види још

Референце

^ Петер M. Фенwицк (1994). „А неw дата струцтуре фор цумулативе фреqуенцy таблес”. Софтwаре: Працтице анд Еxпериенце. 24 (3): 327—336. дои:10.1002/спе.4380240306.
^ Пусхкар Мисхра (2013). „А Неw Алгоритхм фор Упдатинг анд Qуерyинг Суб-арраyс оф Мултидименсионал Арраyс”.

Спољашње везе

[1] Петер M. Фенwицк (1994). „А неw дата струцтуре фор цумулативе фреqуенцy таблес”. Софтwаре: Працтице анд Еxпериенце. 24 (3): 327—336. дои:10.1002/спе.4380240306.

[2] Пусхкар Мисхра (2013). „А Неw Алгоритхм фор Упдатинг анд Qуерyинг Суб-арраyс оф Мултидименсионал Арраyс”.

[1]

[2]