2BIT-ReadSingle

Molim za pomoć. Reč je o 2BIT strukturi. Nikako ne mogu da sklopim algoritam za
'ReadSingle(x,y)', tj. određivanju vrednosti na poziciji (x,y). Ili , jednostavno, koristiti još jednu tabelu u kojoj su samo vrednosti na poz (x,y). Jasno mi je za jednodimenzionalnu strukturu, ali n-dim, hm...
Hvala unapred.

hehe .. nadam se da pricas o kumulativnim u 2d ( binary indexed trees ), ako ne reci pa cu izbrisati ovo :)

int read( int x, int y, int x2, int y2 )
{
x--;
y--;
  return get( x, y ) - get( x, y2 ) - get( x2, y ) + get( x2, y2 );
}

int get( int x, int y )
{
int ret = 0;
for ( int i = x; i > 0; i -= ( i & -i ) )
 for ( int j = y; j > 0; j -= ( j & -j ) )
     ret += S[ i ][ j ];
return ret;
}

dakle da bi ucitao readsingle( x, y ), trebas da pozoves
read( x, y, x, y );

Upravo sam primetio da radis u pascalu, nadam se da mozes da citas c/c++, ako ne mozes reci, pa cu napisati ovo u pascalu

ovo read(), radis po principu ukljucenja iskljucenja, npr. za 3d

int read( int x, int y, int z, int x2, int y2, int z2 )
{
x--; y--; z--;
return get( x, y, z ) - get( x, y, z2 ) - get( x, y2, z ) - get( x2, y, z ) + get( x, y2, z2 ) + get( x2, y2, z ) + get( x2, y, z2 ) - get( x2, y2, z2 ).
}
int get( int x, int y, int z )
{
int res = 0;
for ( int i = x; i > 0; i -= ( i & -i ) )
for ( int j = y; j > 0; j -= ( j & -j ) )
for ( int k = z; k > 0; k -= ( k & -k ) )
  res += S[ i ][ j ][ k ];
return res;
}

ako gresim, molim vas ispravite me. :)

Hvala ti na odgovoru. Nemam problema, što se tiče C-a. Ovo što si napisao je apsolutno OK i mislim da shvatam. Ali, nisam jasno postavio pitanje. Naime, kod kumulativnih tabela, dodavanjem člana na poziciju i,j (neka je ta vrednost x(i,j)), sređuju se vrednosti tabele S, na osnovu koje dobijamo zbir članova x(i,j). I to je ono što si napisao. Pitanje: da li je moguće dobiti vrednost člana x(i,j) na osnovu tabele S, tj bez korićenja tabele x? Ako se želi promeniti vrednost x(i,j), moze se do uraditi na dva načina: 1.) dodavanjem 'newvalue - x(i,j)' na poziciju (i,j) i tabela S se ažurira na istom procedurom. 2) naći vrednost x(i,j), zatim srediti S sa '-x(i,j)', pa sa '+newvalue'.
Ova dva načina daju isti rezultat, ali kad je reč o operaciji sabiranja. Ali, ako je u pitanju složena operacija, onda (mislim) da se mora raditi na drugi način.
Uh, nadam se da sam bio jasniji nego prvi put. Recimo, pogledaj zadatke MATSUM i Z-PRODUCT (mislim da su analogni). Kod matsum u pitanju je sabiranje, a kod z-product množenje. Pomislio sam da sa z-product utvrdim gradivo, ali ....

pa nisam siguran da i dalje razumem tvoje pitanje ...

da li mislis na ovo:

npr. imas u 1d...
i onda ti je x[ i ] = get( i ) - get( i-1 ) ?
( ovo moze brze )

ako je to:
za 2d: x[ i ][ j ] = read( i, j, i, j )...
tj.
x[ i ][ j ] = get( i-1, j-1 ) - get( i-1, j ) - get( i, j-1 ) + get( i, j );
( i ovo moze brze )

ako nije ovo onda daj primer neki pa cu lakse razumeti tvoje pitanje

Uu, al sam se zaglupio. To je odgovor na moje pitanje. Ma ja uporno pokušavam da složim proceduru od par redova (barem sam tako mislio) za tvoj odgovor:

x[ i ][ j ] = get( i-1, j-1 ) - get( i-1, j ) - get( i, j-1 ) + get( i, j );
( i ovo moze brze )

Hvala ti.