Ova implementacija strukture

I ova struktura implementirana u jeziku c++ će točno odrađivati sve operacije koje smo zahtjevali.

class Struktura {
  vector<int> a;

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

  void dodaj(int x, int v) {
    for (int i = x; i < a.size(); ++i)
      a[i] += v;
  }

};

Broj operacija potrebnih za dodavanje elementa u strukturu je sada veći od 1! Točnije, moramo napraviti N - x koraka, što je proporcionalno sa N.

Dakle u ovoj implementaciji na svakom mjestu pamtimo sumu svih vrijednosti na njemu i lijevo od njega. To nam vrlo lijepo odgovara za dobiti sumu vrijednosti, no kod dodavanja se moramo pitati:

U ovom slučaju odgovor je mjestu x i svim mjestima desno od njega.

Simulacija operacija

000000
000000

Rezultat: a[2] = 0

Sva mjesta čijoj ću sumi doprinjeti moram povećati za 4. To su mjesta 3,4,5,6.

004444
004466

Sva mjesta čijoj ću sumi doprinjeti moram povećati za 2. To su mjesta 5,6.

004466

Rezultat: a[5] = 6

004466

Rezultat: a[4] = 4

© 2012. Anton Grbin Creative Commons License

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