Moze li ko da mi pojasni o cemu je stvar ovdje? Ako ne grijesim z-magija zahtjeva rad sa komulativnim tabelama, pa bi bio zahvalan ako bi mi ko mogao objasniti malo o ovome.
Kumulativne tabele?
Moze ti pomoci http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees
Taj zad moze da se resi i intervalnim stablima, samo je malo sporije.
Taj zad moze da se resi i intervalnim stablima, samo je malo sporije.
Moze li neko reci gdje se moze pogledati nosto o tim tablicama. Iako se zadatak moze uraditi drugacije, zanima me sta su te tablice jer do sada za njih nisam cuo.
imas link u bobinom postu
Moje isprike, kad sam vidio na kraju linka "binaryIndexedTrees", mislio, sam da to nema veze sa ovom temom.
Drugi put cu prvo provjerit. :D
Drugi put cu prvo provjerit. :D
Moze li netko pojasniti ove bitovne operacije u datom tutorijalu?
mbalunovic: U potpunosti te razumijem...
znaci dok dodajes broj u "tabelu" dodajes ga svakom članu koji pri podjeli na proste faktore ima jednu dvojku vise, kako imas x+(x&-x), znaci, za primjer uzmimo 8, 1000, -8, 1111 i sad 8&-8 =1000, tj 8 pa taj broj prvo dodas 8. clanu polja, onda trenutnoj poziciji dodas (x&(-x)) i to radis sve dok je taj novi broj <=n.
Dok racunas sumu moras raditi obratno, znaci zbrajati sve vrijednosti koje se nalaze na poljima na koja si prije dodavao, a to mozes tako da kad maknes zadnju jedinicu vrsis "i" operaciju, za 8, 8&(8-1) tj. 1000 & 0111 a to je 0 tako da ces samo zbrojiti onu vrijednost na polju 8.
npr. dodajemo 3 na 5 mjesto, (n velicina tabele)
x=5
tabela[x]+=3
x+=x&(-x)
if(x<=n) vratis se na pocetak
zapis je gotov
a dok recimo hoces sumu prvih 5 clanova:
x=5;
suma+=tabela[x];
x=x&(x-1);
if(x>0) vratis se na pocetak
ispis sume;
Ako sam sto fulao, slobodno me ispravite , jer je i meni sve to novo
Dok racunas sumu moras raditi obratno, znaci zbrajati sve vrijednosti koje se nalaze na poljima na koja si prije dodavao, a to mozes tako da kad maknes zadnju jedinicu vrsis "i" operaciju, za 8, 8&(8-1) tj. 1000 & 0111 a to je 0 tako da ces samo zbrojiti onu vrijednost na polju 8.
npr. dodajemo 3 na 5 mjesto, (n velicina tabele)
x=5
tabela[x]+=3
x+=x&(-x)
if(x<=n) vratis se na pocetak
zapis je gotov
a dok recimo hoces sumu prvih 5 clanova:
x=5;
suma+=tabela[x];
x=x&(x-1);
if(x>0) vratis se na pocetak
ispis sume;
Ako sam sto fulao, slobodno me ispravite , jer je i meni sve to novo
ovdje je lijepo objašnjeno s kodom:
http://www.elitesecurity.org/t80503-
http://www.elitesecurity.org/t80503-
neznam zasto spominjes proste faktore..uglavnom
x & -x ce ti dati najdesniju jedinicu u binarnoj prezentaciji broja x...
x & -x ce ti dati najdesniju jedinicu u binarnoj prezentaciji broja x...
Radio sam z-magiju kumulativnim tablicama ali mi nijedan primjer nije tocan :/
sve je isto kao i u pravim tablicama samo sto
tree[y + y & (-y)] smanjim za jedan...
sve je isto kao i u pravim tablicama samo sto
tree[y + y & (-y)] smanjim za jedan...
Hm, stvarno mi ne idu u glavu ove tabele, uopste neshvatam ove bitovne operacije kako funkcionisu.. vec danima pokusavam da ih shvatim.