Ova struktura podataka jednostavnija je za konstrukciju od logaritamske strukture i može odgovarati na agregacijske upite u nekom intervalu.
Tako naprimjer, pomoću ove strukture moći ćemo u logaritamskom vremenu odgovoriti na upite:
Isto tako, u najjednostavnijem obliku moći ćemo u istom vremenu dodavati vrijednosti na pojedinačne elemente.
Agregacijski operator je neki asocijativni operator puput zbrajanja, množenja, minimuma i maksimuma. Svaki agregacijski operator ima svoj neutralni element. Za zbrajanje to je , za množenje , a za minimum .
U daljnjem tekstu pretpostaviti ćemo da za agregacijski operator imamo zbrajanje.
Tournament stablo u najjednostavnijem obliku imati će sljedeće sučelje:
struct tournament_tree { tournament_tree(int n); void add(int pos, int v); int query(int lo, int hi) const; };
Metoda add dodaje na mjesto pos vrijednost v, dok metoda query pronalazi sumu brojeva u isključenom intervalu [lo, hi>. Ključna riječ const nakon deklaracije metode query garantira da se stablo neće promijeniti ako na njemu napravimo upit.
Pretpostavimo da želimo izgraditi torunament stablo nad nizom brojeva .
Članove niza postavljamo u listove potpunog binarnog stabla. Budući da potpuno binarno stablo ima listova, primjećujemo da možemo povećati na prvu potenciju broja dva uz istu dubinu stabla. U daljnjem tekstu smatramo da je potencija broja .
Čvorove stabla označimo prirodnim brojevima po dubinama s lijeva na desno. U takvom označavanju vrijedi:
U primjeru na slici niz velik je , i njegovi članovi zapisani su u čvorovima s oznakama od do . Primjetimo da čvor s oznakom nema pridruženi element niza , i da uz istu dubinu stabla možemo rukovati s nizom veličine .
Svaki čvor pamtiti će sumu svih listova u njegovom podstablu. Tako će npr. čvor s oznakom biti zadužen za pamćenje sume elemenata X[2] + X[3] dok će čvor s oznakom pamtiti sumu elemenata X[4] + X[5] + X[6] + X[7], ako postoji X[7].
Primjetite kako korjen stabla pamti agregirane vrijednosti za sve listove. Isto tako, primjetite kako se vrijednost jednog lista pamti u točno čvorova-roditelja, slično kao u logaritamskoj. Vrijednost u listu s oznakom biti će sadržana u čvorovima .
Budući da se radi o potpunom binarnom stablu, agregiranu vrijednost u unutarnjem čvoru s oznakom možemo dobiti tako da agregiramo vrijednosti koje nalazimo u njegovoj djeci. U našem slučaju sume, neka u a[i] piše suma koju pamti unutarnji čvor s oznakom i. U svakom trenutku mora vrijediti a[i] = a[i * 2] + a[i * 2 + 1].
Imajući na umu gore navedeno, operacija promjene nekog elementa u nizu je jednostavna: potrebno je promijeniti list koji pamti taj element i osvježiti vrijednosti za sve roditelje. Dosjetka kojom ćemo se koristiti je da ćemo sve vrijednosti pamtiti u jednom nizu. Originalni elementi niza biti će postavljeni u tom nizu s pomakom (potencija broja ), odnosno u listovima stabla.
Stoga je implementacija za promjenu nekog elementa:
void add(int pos, int v) { pos = pos + N; // u nizu a koji predstavlja stablo, element originalnog niza pos nalazi se na lokaciji a[pos + N] a[pos] = a[pos] + v; // povecajmo zeljeni element za v. for (pos /= 2; pos > 0; pos /= 2) // osvjezimo sve roditelje a[pos] = a[pos * 2] + a[pos * 2 + 1]; }
Složenost promjene je dubina stabla, odnosno .
Kako bi odgovorili koja je suma brojeva u bilo kojem intervalu [lo,hi>, možemo primjetiti kako se taj interval može razbiti na neke disjunktne podintervale čije su duljine potencije broja . Ako to uspijemo, onda je samo potrebno pozbrojiti vrijednosti u čvorovima koji pamte sume u tim podintervalima.
Pokazuje se da se svaki interval može razbiti na najviše takvih intervala, i to razbijanje radimo rekurzivno. Pozivamo se za korjen stabla i onda odlučujemo:
Kako bi izbjegli ponovno računanje donjih i gornjih granica intervala za koje je zadužen trenutni čvor, tu vrijednost šaljemo u rekurziju:
int query(int node, int node_lo, int node_hi, int query_lo, int query_hi) { if (node_lo >= query_lo && node_hi <= query_hi) return a[node]; if (node_lo >= query_hi || node_hi <= query_lo) return 0; int mid = (node_lo + node_hi) / 2; return query(node * 2, node_lo, mid, query_lo, query_hi) + query(node * 2 + 1, mid, node_hi, query_lo, query_hi); } // sumu u intervalu [lo, hi> dobijemo pozivom query(1, 0, N, lo, hi);
struct tournament_tree { tournament_tree(size_t n) { for (offset = 1; offset < n; offset *= 2); a.resize(2 * offset); } void add(int pos, const int &v) { pos += offset; a[pos] = a[pos] + v; for (pos /= 2; pos; pos /= 2) a[pos] = a[pos * 2] + a[pos * 2 + 1]; } int query(int qlo, int qhi) const { return query(1, 0, offset, qlo, qhi); } private: int query(int v, int lo, int hi, int qlo, int qhi) const { if (lo >= qlo && hi <= qhi) return a[v]; if (lo >= qhi || hi <= qlo) return 0; return query(2 * v, lo, (lo + hi) / 2, qlo, qhi) + query(2 * v + 1, (lo + hi) / 2, hi, qlo, qhi); } size_t offset; vector<int> a; };
Pogledajte i genericku implementaciju ove strukture na
https://github.com/lukakalinovcic/kodiranje/blob/master/lib/range_statistic/
Ovaj članak objavljen je pod
Creative Commons Attribution-ShareAlike 3.0 Croatia License