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:

suma elemenata u intervalu, što može i logaritamska
najmanji broj u intervalu, slično kao što to radi i konstantna struktura.
najdesniji ne-nul element u intervalu
bilo koju agregaciju na intervalu

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:

krojen ima oznaku
svaki unutarnji čvor s oznakom ima djecu s oznakama i
listovi imaju oznake

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:

ako je interval koji pamti trenutni čvor cijeli u traženom intervalu, vrati vrijednost koja je zapisana u čvoru
ako je interval koji pamti trenutni čvor cijeli izvan traženog intervala, vrati neutralni element (u našem slučaju )
ako se trenutni i traženi interval djelomično preklapaju rekurzivno se pozovi za djecu i agregiraj dobivene rezultate

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/

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