Buna!
Imi poate explica cineva cum functioneaza sumele partiale in matrice? Nu inteleg nicicum algoritmul acesta:
int n,m, A[1001][1001], S[1001][1001];
//citire n,m,A[][]
for(int i = 0 ; i <= n ; i ++)
S[i][0] = 0;
for(int j = 0 ; j <= m ; j ++)
S[0][j] = 0;
for(int i = 1 ; i <= n ; i ++)
for(int j = 1 ; j <= m ; j ++)
S[i][j] = S[i-1][j] + S[i][j-1] - S[i-1][j-1] + A[i][j];
int is,js; // coltul stanga sus
int ij,jj; // coltul dreapta jos
//citire is,js, ij,jj;
cout << S[ij][jj] - S[is-1][jj] - S[ij][js-1] + S[is-1][js-1];
Multumesc!
Răspunsuri la întrebare
Daca avem o matrice/submatrice cu 4 zone care arata asa:
aaaaaaaabbbbbb
aaaaaaaabbbbbb
aaaaaaaabbbbbb
ccccccccdddddd
ccccccccdddddd
ccccccccdddddd
ccccccccdddddd
Si matricea cu sume este deja construita, atunci putem afla suma tuturor elementelor din zona d, stiind doar coordonatele colturilor stanga sus si dreapta jos astfel :
Prima oara, suma din coltul dreapta jos este suma tuturor elementelor din zonele a,b,c si d.
Apoi, scadem suma tuturor elementelor din zonele a si c, ne raman doar b si d.
Scadem suma tuturor elementelor din zonele a si b, raman (suma tuturor elementelor din zona d) - (suma tuturor elementelor din zona a)
Apoi, adaugam suma tuturor elementelor din zona a si ne ramane suma tuturor elementelor din zona d.
Atunci, daca ij, jj, is, js sunt indicii pentru randul si coloana coltului dreapta jos, respectiv indicii pentru randul si coloana pentru coltul stanga sus, si S matricea cu sumele, avem:
suma tuturor elementelor din zona a = S[is-1][js-1]
suma tuturor elementelor din zona b = S[is-1][jj]
suma tuturor elementelor din zona c = S[ij][js-1]
suma tuturor elementelor din zona d este S[ij][jj] - S[is-1][jj] - S[ij-1][jj] + S[is-1][js-1]
Pentru a construi matricea, avem:
S[i][j] = S[i-1][j] + S[i][j-1] - S[i-1][j-1] + element[i][j]
Impartim iar o submatrice in 4 zone, a,b,c,d
aaaaaaa b
aaaaaaa b
ccccccc d
Atunci, suma tuturor elementelor din aceasta submatrice este:
(suma elementelor din zonele a si c) + (suma elementelor din zonele a si b) - (suma elementelor din zona a) + elementul d.