Evo vam jedna korisna stvar, skoro mi pokazao drug. Radi se o kumulativnim tabelama, pa pošto me je pitao Dragon znam li nešto o tome, da mu i odgovorim ovdje.
Dakle kumulativne tabele su strukture koje vam odgovaraju na pitanje "kolika je suma prvih X elemenata". Dakle ako imate niz od 1000 brojeva, ova struktura može brzo da odgovori na pitanje "suma prvih 100" ili "suma prvih 200" brojeva. Upotreba ove strukture je vrlo korisna, recimo pomoću tako jednostavnog "upita" može se saznati i kolika je suma bilo kojeg intervala, recimo, između A i B, suma iznosi vrijednost u kumulativnoj tabeli za B - vrijednost za A.
E sad, kako se ovo implementira, pa, većina ljudi zna jedan način, a to je da se prilikom računanja sume prvih 100 brojeva npr, jednostavno odradi jedna petlja od 1 do 100 i te vrijednosti saberu. Složenost ove operacije je O(n) (linearna). Mnogo bolje bi bilo napraviti niz suma u kojem ćemo čuvati (keširati) sume svih intervala od 0 do i (0<i<N - broj elemenata). Onda kada nam zatreba vrijednost (kumulativna suma) samo pročitamo vrijednost tog niza.
Pa šta je problem onda, kod ovog prvog, čitanje je O(n) a kod ovog drugog načina je O(1)? Problem je što kod prvog načina, mijenjanje bilo koje vrijednosti nije problem, jer se kumulativna suma svaki put izračunava ponovo, međutim, kod drugog načina, promjena neke vrijednosti utiče na sve kumulativne sume iznad tog indeksa, što znači da je operacija linearna, O(1). Evo vam kako da dobijete složenost O(logN) za oba slučaja:
Ako imamo n elemenata, definišimo N kao n*2, ili ljepše, n << 1.
Napravimo niz int kum[N] i inicijalizujemo sve vrijednosti na 0 (u javi je ovo automatsko, u C-u je najbolje koristiti memset funkciju).
Potrebne su dvije funkcije, jedna za čitanje, druga za upisivanje.
Kod:
int get (int i) {
int r = 0;
while (i > 0) {
r += kum[i];
i -= i & -i;
}
return r;
}
void add (int i, int v) {
while (i < N) {
kum[i] += v;
i += i & -i;
}
}
Sad vi mene recite šta znači, odnosno radi, linija i -= i & -i;
Happy hacking
Prijavite se
Registruj se
FAQ
Pretraga
Jel' tako, Nemanja? 
