RACUNALNIŠ TVO
Fenwickovo drevo
•is ■i' ■i'
Aleksander Kelenc
Opis problema
Neki spletni portal se je odločil, da bo za potrebe analize starosti svojih uporabnikov le-te uvrščal v 15 različnih starostnih kategorij glede na njihovo starost ob prvi prijavi v portal. V tabeli 1 so prikazane posamezne kategorije in ustrezno število uporabnikov, ki so v določenem trenutku uvrščeni v to kategorijo.
Omenjeni portal v različnih trenutkih zanima, koliko njihovih uporabnikov je uvrščenih med dvema izbranima kategorijama, npr. od kategorije 21-25 do kategorije 46-50 (vključno z mejama) je 13 uporabnikov. Seveda se z novimi uporabniki tabela kategorij nenehno spreminja. Ker spletni portal jemlje analizo podatkov zelo resno, želi takšna povpraševanja izvajati kolikor hitro je le mogoče. Dobili smo nalogo, da opišemo podatkovno strukturo, ki bo to omogočala.
Za lažje razmišljanje opišimo podan problem z računalniškim jezikom. Podan imamo končen seznam števil U-1, a.2, ■ ■ ■, a-n. Zanima nas vsota števil med indeksoma i in j (vključno z mejama), kjer velja 1 < i < j < n. Ce si seznam števil shranimo v polje a, potem bomo za eno takšno popraševanje morali pregledati vse elemente polja med indeksoma i in j. V splošnem za eno poizvedbo to pomeni linearno časovno zahtevnost glede na velikost seznama. Ali smo lahko bolj učinkoviti?
Hitro opazimo, da bi si pri tem lahko pomagali s kumulativnimi frekvenčami. Naj bo k polje kumulativnih frekvenč za polje a. Za vsak indeks i, kjer je 1 < i < n, je kumulativna frekvenča ki enaka vsoti vseh elementov od a1 do ai, torej ki = a1 + ... + ai. Za izračun polja k naj bo k1 = a1 in element ki = ki-1 + ai za vsak i G {2,...,n}. Vidimo, da je vsota števil med indeksoma i in j sedaj enaka kar kj - ki-1. Ce izračunamo polje kumulativnih frekvenč, potem dobimo konstantno ča-
sovno zahtevnost za eno poizvedbo vsote elementov med dvema indeksoma. Zelo učinkovito, ampak v portalu se število uporabnikov nenehno spreminja in zato moramo omogočiti še posodabljanje elementov v polju a. Ko posodobimo element ai to pomeni, da moramo v polju kumulativnih frekvenč k posodobiti vse elemente od ki do kn. Vidimo, da v splošnem dobimo linearno časovno zahtevnost za posodobitev polja kumulativnih frekvenč. Z uporaba polja kumulativnih frekvenč smo dobili konstantno časovno zahtevnost za poizvedbo, vendar smo s posodabljanjem elementov spet prišli do linearne časovne zahtevnosti.
Drevesne podatkovne strukture se pri podobnih problemih izkažejo kot zelo učinkovite, saj velikokrat pohitrijo reševanje problema. Razvitih je pre-čej različnih drevesnih podatkovnih struktur in ena izmed njih je tudi Fenwičkovo drevo. Fenwičkovo drevo je podatkovna struktura, ki z uporabo ideje o kumulativnih frekvenčah omogoča poizvedbo za vsoto elementov med dvema indeksoma in posodabljanje elementov polja v logaritemski časovni zahtevnosti glede na velikost polja. Fenwičkovo drevo je leta 1994 prvi predstavil Peter M. Fenwičk.
Osnovna ideja
Osnovna ideja Fenwičkovega drevesa je, da lahko vsako naravno število izrazimo kot vsoto ustreznih potenč števila 2. To pomeni, da bi lahko kumulativno frekvenčo ki predstavili kot vsoto ustreznih delnih kumulativnih frekvenč (predstavimo s poljem f) glede na razčep števila i na vsoto potenč števila 2. Ce lahko indeks i predstavimo kot vsoto treh potenč števila 2, potem bo npr. ki enak vsoti treh delnih kumulativnih frekvenč. Seveda morajo biti delne kumulativne frekvenče podane za ustrezne intervale, da bomo s tem pristopom uspeli sestaviti čelotno kumulativno frekvenčo za indeks i. Za vsako potenčo števila 2 iz razčepa indeksa i bo delna kumulativna frekvenča obsegala interval, ki bo širok toliko, kot,

PRESEK 44 (2016/2017)4	22
RAČU N A L NIŠTVO

starost	do 10	11-15	16-20	21-25	26-30	31-35	36-40	41-45
L"tevilo starost	3 46-50	1 51-55	0 56-60	0 61-65	2 66-70	2 71-75	5 nad 75	3
L"tevilo	1	5	4	0	0	2	3	
TABELA 1.
Tabela kategorij
je vrednost te potence. V zgornjem delu tabele 2 so prikazani intervali za delne kumulativne frekvence do števila 15. Oglejmo si osnovno idejo na konkretnem primeru za indeks 11. Število 11 = 23 + 21 + 20, kar pomeni, da bo k11 sestavljen iz delnih kumulativnih frekvenc za intervale širine 8, 2 in 1 oziroma iz delnih kumulativnih frekvenc za intervale 1..8, 9..10 in 11.
V spodnjem delu tabele 2 lahko vidimo primer, kjer imamo v prvi vrstici zapisano polje a, v drugi vrstici polje za kumulativne frekvence k in v tretji vrstici polje za delne kumulativne frekvence f. Vrnimo se na primer indeksa 11. Kumulativna frekvenca za indeks 11 je sestavljena iz k11 = f11 + f10 + f8, kar ustreza vsoti = a11 + a9..10 + a1..8, kjer je a1..8 = a1 + ... + a8. Zaporedje števil 11,10,8 dobimo, ce v dvojiški predstavitvi števila 11 = 1011 (2) po vrsti nadomeščamo najbolj desno enico z niclo. Izračun kumulativne frekvence ki iz polja delnih kumulativnih frekvenc f torej dobimo tako, da seštejemo vse elemente polja f, ki jih dobimo, ko indeksu i po vrsti nadomešcamo najbolj desno enico z niclo, dokler ne pridemo do števila 0.
Takšno indeksiranje nam iz polja delnih kumulativnih frekvenc generira drevo. Za koren drevesa postavimo indeks 0. Drevo ni uravnoteženo. Vsako vo-zlišce drevesa ima toliko otrok, kot je število nicel do prve enice v dvojiški predstavitvi indeksa, gledano iz desne strani. Globina vozlišca (razdalja do korena) pa je enaka številu enic v dvojiški predstavitvi indeksa. Polje, opremljeno s takšnim indeksiranjem imenujemo Fenwickovo drevo. Zaradi nacina indeksiranja takšno strukturo imenujemo tudi binarno indeksirano drevo. Na sliki 1 je predstavljeno drevo za primer polja velikosti 15. V vozlišcih drevesa so navedeni indeksi, v katerih se nahajajo ustrezni elementi v polju delnih kumulativnih frekvenc.
Operacije
S pomocjo opisane strukture želimo v logaritemskem casu izvajati naslednji dve operaciji:
■ poizvedbo za kumulativno frekvenco do nekega
indeksa i,
posodobitev polja delnih kumulativnih frekvenc f
glede na posodobitev elementa ai.
Pri obeh operacijah bomo indekse racunali s po-mocjo najbolj desne enice v dvojiški predstavitvi. Za izracun najbolj desne enice v dvojiški predstavitvi nekega števila si bomo pomagali z dvojiškim kom-plementom. Z dvojiškim komplementom so v racu-nalniku predstavljena negativna števila. Iz pozitivnega števila m dobimo z dvojiškim komplementom -m tako, da v dvojiški predstavitvi od m obrnemo vse bite in prištejemo ena. V tabeli 3 imamo primer za dvojiški komplement števila 18 = 00010010(2), ki znaša 11101110. Opazimo, da je edino mesto, kjer se enica hkrati pojavi tako v dvojiški predstavitvi števila 18 kot tudi v dvojiški predstavitvi števila -18, ravno mesto najbolj desne enice v obeh dvoji-ških predstavitvah. S pomocjo logicnega operatorja A dobimo rezultat 00000010. Najbolj desno enico indeksa i dobimo z (i A -i), kar pomeni, da v drevesu za poizvedbe indeks starša vozlišca i izracu-namo kot i - (i A - i) .
Poizvedba za kumulativno frekvenco
Spodaj imamo prikazano funkcijo v programskem jeziku C++, ki vrne kumulativno frekvenco za indeks i. Za polje delnih kumulativnih frekvenc uporabimo vector<i nt> f. Število iteracij whi l e zanke je enako številu enic indeksa i v bitni predstavitvi - v drevesu za poizvedbe to predstavlja dolžino poti od vo-zlišca i do korena. V najslabšem primeru to pomeni,
26
PRESEK 44 (2016/2017)4
RACUNALNIŠ TVO
indeks	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
interval	1	1..2	3	1.. 4	5	5..6	7	1..8	9	9..10	11	9..12	13	13..14	15
polje a	3	1	0	0	2	2	5	3	1	5	4	0	0	2	3
polje k	3	4	4	4	6	8	13	16	17	22	26	26	26	28	31
polje f	3	4	0	4	2	4	5	16	1	6	4	10	0	2	3
TABELA 2.
Primer za polje velikosti 1 5
SLIKA 1.
Drevo za poizvedbe na polju velikosti 1 5
18 00010010 11101101 + 00000001 "-18 11101110
TABELA 3.
Dvojiški komplement števila 18
da je časovna zahtevnost funkcije enaka logaritmu velikosti polja a.
int vrniKumulativnoFrekv(int i) { int vsota = 0; while (i > 0) { vsota += f[i];
i -= (i nt) (i & -i); // odštejemo najbolj desno enico
}
return vsota;
}
Ko imamo metodo za izračun kumulativne frekvence za poljubni indeks, potem lahko vsoto elementov med indeksoma i in j izračunamo kot vrni Kumul ativno-Frekv(j)-vrni KumulativnoFrekv(i-1).
Posodabljanje elementa polja
Pri poizvedbi za kumulativno frekvenco smo indeksu vsakic enico na desni strani nadomestili z niclo. S tem smo se premikali proti začetku polja delnih kumulativnih frekvenc oziroma proti korenu drevesa za poizvedbe. Za posodobitev elementa polja a pa moramo posodobiti vrednosti vsem delnim kumulativnim frekvencam, ki vsebujejo ta element. V tabeli 2 poglejmo, katere elemente polja delnih kumulativnih frekvenc f moramo posodobiti, ce v polju a posodobimo elemnent a3. Elementi polja f, katerih intervali vsebujejo element a3, so f3, f4 in f8. Iz indeksa 3 se moramo premakniti na indeks 4 (prištejemo
1) in potem na indeks 8 (prištejemo 4). Opazimo, da namesto odstranjevanja (odštevanja) enega bita na desni strani, moramo k trenutnemu indeksu dodati (prišteti) najbolj desni bit na vsakem koraku. Ta korak ponavljamo, dokler ne pridemo preko velikosti polja.
Z indeksiranjem za posodabljanje elementov dobimo drugacno drevo, kot smo ga dobili z indeksiranjem za poizvedbe. Drevo za polje velikosti 15 je prikazano na sliki 2.
Za koren drevesa dodamo vozlišce z indeksom 16, ki služi kot stražar, pri katerem se moramo zaustaviti pri posodabljanju. Opazimo, da je glede na

PRESEK 44 (2016/2017)4
27
RAČUNALNIŠTVO

3 © © ©
©
SLIKA 2.
Drevo za posodabljanje elementov polja velikosti 1 5
obliko drevo za posodabljanje zrcalna slika drevesa za poizvedbe.
Napišimo še funkcijo v programskem jeziku C++, ki posodobi polje delnih kumulativnih vsot, ce k elementu polja at prištejemo vrednost v, kjer je vrednost v lahko tudi negativna.
void posodobi(int i, int v) { while (i < f.size()) { f[i] += v;
i += (int) (i & -i); // prištejemo najbolj desno enico
}
}
tov v logaritemski Časovni zahtevnosti glede na velikost polja a. V našem primeru starostnih kategorij spletnega portala je polje velikosti 15. V praksi sprememba casovne zahtevnosti iz linearne na logaritemsko pri polju velikosti 15 ne pride do izraza, vendar pa opisano podatkovno strukturo lahko uporabimo za poljubno velikost polja. S povečevanjem velikosti polja pa pridemo do bistvene razlike pri časovni učinkovitosti omenjenih operacij.
Literatura
[1]	P. M. Fenwick, A New Data Structure for Cumulative Frequency Tables, Software-practice and experience 24 3, (1994), 327-336.
[2]	F. Halim in S. Halim, Competitive Programming 3: The New Lower Bound of Programming Contests, 2013.
[3]	Wikipedia: Fenwick tree, ogled: 14. 1. 2017. https://en.wiki pedi a.org/wi ki/Fenwi ck_ tree.
_ XXX
Barvni sudoku
Časovno zahtevnost funkcije za posodabljanje lahko ocenimo s pomocjo casovne zahtevnosti funkcije poizvedbe. Število iteracij while zanke je enako dolžini poti od vozlišca i do korena v drevesu za posodabljanje. Ker je drevo za posodabljanje zrcalna slika drevesa za poizvedbe, sledi, da je najslabša ca-sovna zahtevnost metode void posodobi(int i, i nt v) prav tako enaka logaritmu velikosti polja a.
S tem smo opisali podatkovno strukturo, ki omo-goca, da za podano polje števil a izvajamo poizvedbe za kumulativne vsote in posodabljanje elemen-

3
v
O □
m
>
a.
<
m
>
m H
-> >00 * £
-> a
1	7	4	6	5	382		
3	5	8	2		6 7 4		
2	3	6	8	7	1	4	5
7	4	5	1	3	2	6	8
6	2	7	4	8	5	1	3
5	8	1	3	4	7	2	6
4	6	3	7	2	8	5	1
8	1	2	5	6	4	3	7
XXX
28
PRESEK 44 (2016/2017)4