子矩阵的和

【问题描述】

　　给出一个n*m的矩阵，多次询问子矩阵中数字之和。

【输入格式】

　　第一行包含三个正整数n, m, k(n, m<=5000, k<=10000)，分别表示矩阵行数和列数以及询问次数。

　　接下来的n行，每行包含m个整数（整数不超过10000），描述该矩阵。

　　接下来的k行询问，数据描述子矩阵左上角坐标（x1, y1）,以及右下角坐标（x2, y2）。

【输出格式】

　　共k行，每行一个整数，表示询问的子矩阵数字之和。

【输入样例】

3 4 2
-8 4 10 -15
9 12 -3 5
11 -5 -7 -4
3 2 3 3
1 1 3 2

【输出样例】

-12
23

【算法思想】

计算矩阵的前缀和：s[x][y] = s[x - 1][y] + s[x][y -1] - s[x -1][y-1] + a[x][y]
在这里插入图片描述
计算子矩阵的和：s = s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - ][y1 -1]

代码实现

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int N = 1010;
 4 int a[N][N],s[N][N];
 5 int main()
 6 {
 7     int n, m, q;
 8     cin >> n >> m >> q;
 9     for(int i = 1; i <= n; i++)
10         for(int j = 1; j <= m; j++)
11         {
12             scanf("%d", &a[i][j]);
13             s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
14         }
15     while(q--)
16     {
17         int x1, y1, x2, y2;
18         scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
19         printf("%d
", s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]);
20     }
21     return 0;
22 }

3 4 2
-8 4 10 -15
9 12 -3 5
11 -5 -7 -4
3 2 3 3
1 1 3 2