之前讲了一维层面的前缀和数组，这次来讲讲二维的前缀和数组。而每一个位置都表示从起点开始到当前位置之内所有数的和。
我们也很容易观察到，若我们想要对其进行初始化只需要，用上部分的和加上左部分的和，由于中间部分算了两次由此需要扣掉一次，即s[i,j] = a[i, j] + s[i, j-1] + s[i-1, j] - s[i-1, j-1]。
初始化之后要求子矩阵的和就只需要用红色部分减去两个绿色的部分，最后把重复减去的部分再加回来就可以了。即 s [x1y1,x2y2] = s[x2,y2] - s[x2,y1-1] - s[x1-1,y2] + s[x1-1,y1-1]
最后上代码
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int N = 1010; int a[N][N], s[N][N]; int n, m, q; int main() { scanf("%d%d%d", &n, &m, &q); for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { scanf("%d", &a[i][j]); } } 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]; } } while (q--) { int x1, y1, x2, y2; scanf("%d%d%d%d", &x1, &y1, &x2, &y2); //求子矩阵的和 printf("%d\n", s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1]); } return 0; }
