Logaritamska struktura

[ NrmMyth @ 12.05.2006. 19:38 ] @

Trebam informacija o takozvanoj logaritamskoj strukturi.

Hvala.

[ emiraga @ 13.05.2006. 15:35 ] @

Ja se nadam da mislis na Kumulativne sume sa logaritamkom strukturom

evo o jednog topic-a
http://www.elitesecurity.org/tema/80503/

u njemu ima link do dobrog pdf-a
http://www.cs.ubc.ca/local/rea...95/spe/vol24/issue3/spe884.pdf

ideja je da se brzina _citanja_ elemenata iz kumulativne sume _uspori_
u zamjenu da se brzina _promjene_ neke vrijednosti _ubrza_

i to sa obje kompleksnosti

_{[Ovu poruku je menjao emiraga dana 13.05.2006. u 16:40 GMT+1]}

[ NrmMyth @ 13.05.2006. 18:50 ] @

znam sigurno da logaritamska struktura ima

za citanje i upisivanje
pogledati cu linkove pa javim

[ NrmMyth @ 13.05.2006. 21:15 ] @

Je to je bilo to, hvala.

[ Relaja @ 15.05.2006. 21:08 ] @

Ja to radim ovako..Ponekad se moze prilagoditi da bude optimalnije od Kum. Tab.
kao recimo u zadatku "reli" sa saveznog ove godine..
Sa kum.tab. treba obaviti n*2*log(n) a na "moj" nacin n*log(n) + n

//INACE!

Code:

void set(int x){
    l=1,r=n;
    do{
        m=(l+r)>>1; // m=(l+r)/2;
        if(x<=m){
            A[m]++;
            r=m-1;
        }else
            l=m+1;
    }while(l<=r && m!=x);
}

int get(int x){
    l=1,r=n,tr=0;
    do{
        m=(l+r)>>1; // m=(l+r)/2;
        if(x>=m){
            tr+=A[m];
            l=m+1;
        }else
            r=m-1;
    }while(l<=r && m!=x);
    return tr;
}

//U Reli-ju

Code:

int getset(int x){
    l=1,r=n,tr=0;
    do{
        m=(l+r)>>1;
        if(x<=m){
            A[m]++;
            r=m-1;
        }else{
            tr+=A[m];
            l=m+1;
        }
    }while(l<=r && m!=x);
    return tr;
}

[ NrmMyth @ 16.05.2006. 11:01 ] @

I na DMIH-u je ove godine bio zadatak koji se rijesava kumulativnim tablicama.
Sta su zapeli za to?! :)

[ RooTeR @ 16.05.2006. 12:38 ] @

Reli nije morao da se reshava kumulativnim tablicama (ja sam ga radio kao merge sort).
A ovaj sa dmih (3. zadatak drugog dana ako se dobro secam) se slazem da najjednostavnije ide preko ktabela ...

[ NrmMyth @ 16.05.2006. 15:54 ] @

Citat:

RooTeR:A ovaj sa dmih (3. zadatak drugog dana ako se dobro secam) se slazem da najjednostavnije ide preko ktabela ...

Da.

[ Relaja @ 16.05.2006. 18:17 ] @

Citat:

RooTeR: Reli nije morao da se reshava kumulativnim tablicama (ja sam ga radio kao merge sort).

Znam da nije morao.
Posuzio mi je kao primer..

[ panjevic @ 02.06.2006. 23:53 ] @

HAHAHAHAHAHA, evo kezim se dok gledam sta vi uzimate kao primer za kumulativne sume. Inace, reli moze da se uradi na jedno osam nacina... merge sort, stane u 10 redova. A ja sam svima koji urade reli obecao COKOLADU! Dobar primer za primenu kumulativnih suma je jedan zadatak sa mobilnom mrezom sa olimpijade iz finske 2002. Koga interesuje neka gugla, zadatak koristi 2D kumulativne sume i extra je. Inace, finci su te godine izdali bilten sa svim zadacima i svim PREDLOZIMA i ko hoce moze da nauci masu fora iz tog pdfa.

[ RooTeR @ 04.06.2006. 00:37 ] @

A ko je uradio reli koristeci merge sort, dobio je dve chokolade :) (bar sam ja dobio:)