Tournament stablo

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.

Sučelje strukture

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.

Konstrukcija stabla

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:

_anonymous_011221--2331--3442--4552--5663--6773--78 : X[0]8 : X[0]4--8 : X[0]9 : X[1]9 : X[1]4--9 : X[1]10 : X[2]10 : X[2]5--10 : X[2]11 : X[3]11 : X[3]5--11 : X[3]12 : X[4]12 : X[4]6--12 : X[4]13 : X[5]13 : X[5]6--13 : X[5]14 : X[6]14 : X[6]7--14 : X[6]15 : --15 : --7--15 : --

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 .

Autoritet čvora

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].

Implementacija

Promjena

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 .

Upit

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);

Implementacija

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/

© 2006. Luka Kalinovčić
2014. Anton Grbin
Creative Commons License

Ovaj članak objavljen je pod
Creative Commons Attribution-ShareAlike 3.0 Croatia License