所以
r[3,3] = r[2,3]+r[3,2]-r[2,2]+a[3,3];
也就是54 = 33+21-12+12
int r[n+5][m+5],s ; //r数组为前缀和,下标+5,防止数组越界,s为原数组 for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) r[i][j] = r[i-1][j]+r[i][j-1]-r[i-1][j-1]+s[i][j]
所以红色区域的和为:
r[4][4]-r[4][1]-r[2][4]+r[2][1] = 144-30-32+5 = 87 int x1,y1,x2,y2; //x1,y1左上角 x2,y2右上角 cin>>x1>>y1>>x2>>y2; r[x2][y2]-r[x2][y1-1]-r[x1-1][y2]+r[x1-1][y1-1];
#转载请注明出处!