Interval fenwick

Obavezno pročitati prije:

Kada je potrebno postići logaritamsku vremensku složenost za ubacivanje elemenata u niz i traženje rezultata sume nad nekim intervalom u nizu tada se može koristiti fenwickovo stablo. Ubacivanjem elementa u fenwickovo stablo smatramo pribrojavanje broja na neku poziciju .

Ponekad želimo nadodati broj svim elementima u nekom intervalu . Ako koristimo obično fenwickovo stablo tada je vremenska složenost ubacivanja nekog broja na cijeli interval . Postavlja se pitanje: može li se napraviti struktura podataka koja u logaritamskom vremenu ubacuje element u neki interval i koja u logaritamskom vremenu računa sumu u proizvoljnom intervalu.

Definicija strukture koju pokušavamo izgraditi

Struktura mora u složenosti podržavati sljedeće operacije:

Izvod

Jedno od rješenja je tournament stablo s propagacijom tj. nadogradnja tournament stabla s lijenom evaluacijom. Problem ovog pristupa je težina implementacije, tj. duljina koda i otežano traženje grešaka. Drugi pristup je intervalno fenwickovo stablo. Zapravo se radi o dva obična fenwickova stabla koja pamte početke i krajeve intervala. Idemo prvo pogledati koja je generalna ideja, a kasnije ćemo na tu ideju primijeniti obično fenwickovo stablo. Zapisujemo broj na interval . Za početak pogledajmo upite oblika , gdje je s označena početna pozicija. može biti (prema tipu upita):

  1. manje od i tada je odgovor upita
  2. može biti veći ili jednak tada je odgovor
  3. ako je između i tada je odgovor .

Sumu u intervalu možemo pronaći na sljedeći način: upit([a,b]) = upit([1,b]) - upit([1, a-1]). Kao što vidimo problem se svodi na upit oblika . Kako bismo mogli pamtiti intervale koje smo ubacili koristimo dva niza: i . Niz brinut će se za slučajeve drugog tipa, a niz za slučajeve trećeg tipa. Kada ubacujemo u interval :

  1. U niz upišemo:
  2. U niz upišemo:

Upite [1, c] računamo na sljedeći način:

Provjerimo da li ovakvo izračunavanje upita zaista daje točne odgovore:

  1. Ako je c manje od a, tada svi elementi do c su 0 pa ovaj slučaj nije zanimljiv
  2. Ako je c veći ili jednak b tada je
    • jer i , tj. njihova suma je .
    • , što je točan odgovor na upit drugog tipa.
  3. Ako je c između a i b tada je
    • što je točan odgovor za upite trećeg tipa.

Sad smo provjerili da li formula za upit dobro radi ako smo prije toga ubacili samo jedan interval. Pravimo se na tren da za svaki novi interval koji ubacujemo stvaramo dva nova niza i . Označimo intervale koje smo ubacili s i neka ih ima . Neka je upit za jedan interval. Tada je odgovor na upit kolika je suma u intervalu za sve intervale koje smo ubacili: .

Prema ovom izvodu vidimo da sve intervale možemo spremati u iste nizove i . Pravila za ubacivanje su tada:

  1. U niz upišemo:
  2. U niz upišemo:

Formula za upit ostaje ista. Ako bolje pogledamo formulu, ona uvijek traži sume u nizovima i . Potrebno je uočiti da taj problem možemo riješiti pomoću Fenwickove strukture u logaritamskoj vremenskoj složenosti. Dakle, potrebne su nam dvije Fenwickove strukture, jedna koja se brine za niz i druga koja se brine za niz . Dakle dobili smo tražene vremenske složenosti.

Kada ne bi koristili Fenwickovo stablo, nego bi i direktno implementirali pomoću nizova, tada bi vremenska složenost za upit bila , a vremenska složenost za ubacivanje , što je dobro ako je broj ubacivanja puno veći od broja upita.

Ukratko ponovimo što smo napravili: Potrebno je bilo smisliti strukturu koja u logaritamskom vremenu ubacuje intervale i daje odgovore na upite također u logaritamskom vremenu. Ideja je bila da na pametan način označavamo početak i kraj niza i to smo obavili s dva niza. Upit koji vršimo nad ta dva niza koristi sumu od prvog elementa do nekog traženog, gdje uočavamo da je upit moguće implementirati pomoću Fenwickovog stabla u logaritamskoj vremenskoj složenosti, zbog čega dobivamo i logaritamsku vremensku složenost za ubacivanje.

Implementacija

Pomocne strukture
fenwick_tree mul; //Fenwickovo stablo za mul
fenwick_tree add; //Fenwickovo stablo za add
Operacija ubacivanja intervala
void ubaci(int x, int a, int b) {
  mul.ubaci(x, a);
  mul.ubaci(-x, b);
  add.ubaci(-x * (a - 1), a);
  add.ubaci(x * b, b);
}
Operacija upita
int upit(int x) {
  return mul.upit(x) * x + add.upit(x);
}

int upit(int a, int b) {	
  return upit(b) - upit(a - 1);
}

Zadaci

Izvor

© 2014. Dino Šantl Creative Commons License

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