基础算法8——二维前缀和求子矩阵的和

Subject:已知子矩阵左上角断点(x1,y1),右下角端点(x2,y2),求子矩阵中所有数的和。输入：1

步骤：

1.求s[x][y],x,y是子矩阵右下角坐标:

公式：s[x][y]=s[x-1][y]+s[x][y-1]-s[x-1][y-1]+mat[x][y]。

2.求ans=s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1]:

eg.

#includeint mat[1009][1009] = { 0 }, s[1009][1009] = { 0 };int main(){ int m, n, q, x1, x2, y1, y2, h, l; scanf("%d %d %d", &n, &m, &q); for (h = 1; h <= n; h++)//从1开始 { for (l = 1; l <= m; l++) { scanf("%d", &mat[h][l]); }   } //求s for (h = 1; h <= n; h++) { for (l = 1; l <= m; l++) { s[h][l] = s[h][l - 1] + s[h - 1][l] - s[h - 1][l - 1]+mat[h][l]; } } //询问q while (q--) { scanf("%d%d%d%d", &x1, &y1, &x2, &y2); printf("%dn", s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1]); } return 0;}