Logaritamska struktura - tutorial

U ovom tutorijalu ćemo promatrati logaritamsku strukturu koja pamti sumu. Takva struktura podržava sljedeće operacije:

Simulacija za pojašnjenje operacija logaritamske strukture

Spora implementacija je rješenje koje nam vjerojatno odmah pada napamet: pamtiti vrijednosti brojeva na svim mjestima i zbroj izračunati obilazeći sva mjesta do x.

Brzinu operacije zbroj možemo poboljšati tako da ne pamtimo vrijednosti brojeva na svim mjestima, već da na svakom mjestu pamtimo sumu svih vrijednosti do mjesta 1. No u ovoj implementaciji operacija dodaj je puno sporija.

Primjetite da su dvije navedene implementacije u nekim slučajevima i dobre:

No, ako imamo mnogo operacija obje vrsti, potrebno će biti naći kompromis između ove dvije krajnosti.

Logaritamska struktura

Svako mjesto u logaritamskoj strukturi pamti sumu vrijednosti na sebi i na nekim mjestima lijevo od sebe. Struktura je tako konstruirana da je broj vrijednosti čiju sumu pamti svako mjesto najviše .

mjesto 1123456789101112
mjesto 2123456789101112
mjesto 3123456789101112
mjesto 4123456789101112
mjesto 5123456789101112
mjesto 6123456789101112
mjesto 7123456789101112
mjesto 8123456789101112
mjesto 9123456789101112
mjesto 10123456789101112
mjesto 11123456789101112
mjesto 12123456789101112

Ovom tablicom je prikazano koje vrijednosti pamti svako mjesto u logaritamskoj strukturi. Nekoliko primjera:

pseudo kod za sumu i dodavanje vrijednosti

Koristiti ćemo tri funkcije:

suma(x) =
  ako je x == 0, onda je rješenje 0.
  inače, rješenje je suma na mjestu x + suma(x - koliko_pamti(x))

dodaj(x, v) =
  ako je x veći od N, kraj.
  u sumu koje pamti mjesto x dodaj vrijednost v
  dodaj(x + koliko_pamti(x), v)

Pogledajmo izvođenje upita za suma(11).

Vidimo da smo u tri koraka, pokupili u sumu sve vrijednosti iz strukture do mjesta 11.

Izvođenje upita dodaj(5, 10). Ova operacija mora obići sva mjesta koja u svojoj sumi pamte vrijednost mjesta 5.

Funkcija pomaka

Vidimo da se funkcija koliko_pamti koristi i u operaciji dodavanja i u operaciji zbrajanja. Zato je nužno da se ona izvede efikasno. Promatrajući tablicu možemo vidjeti da je vrijednost ove funkcije zapravo vrijednost koju nosi najdesnija jedinica u binarnom rastavu broja. Npr:

Dakle, funkcija pomaka je uvijek potencija broja dva. Postavlja se pitanje kako efikasno izračunati ovu vrijednost?

Konačno rješenje

Ova implementacija koristi rekurzivne pozive u metodama upita te ju je moguće malko ubrzati koristeći iterativni pristup.

class LogaritamskaStruktura {
  vector<int> a;

 public:
  LogaritamskaStruktura(int n) : a(n + 1, 0) {}
  
  int zbroj(int x) {
    return x ? a[x] + zbroj(x - (x&-x)) : 0;
  }

  void dodaj(int x, int v) {
    if (x >= a.size()) return;
    a[x] += v;
    dodaj(x + (x&-x), v);
  }
};
© 2012 Anton Grbin Creative Commons License

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