acwing算法基础课——子矩阵的和
对于每个询问输出子矩阵中所有数的和。
输入格式
第一行包含三个整数 n，m，qn，m，q。
接下来 nn 行，每行包含 mm 个整数，表示整数矩阵。
输出格式
数据范围
1≤n,m≤10001≤n,m≤1000, 1≤q≤2000001≤q≤200000, 1≤x1≤x2≤n1≤x1≤x2≤n, 1≤y1≤y2≤m1≤y1≤y2≤m, −1000≤矩阵内元素的值≤1000
输入样例：
3 4 3 1 7 2 4 3 6 2 8 2 1 2 3 1 1 2 2 2 1 3 4 1 3 3 4
输出样例：
17 27 21
题解：
#include<iostream>
using namespace std;
const int N = 1010;
int a[N][N];
int s[N][N];
int main()
{
int n, m, q, i, j;
cin >> n >> m >> q;
for (i = 1; i <= n; i++)
for (j = 1; j <= m; j++)
scanf("%d", &a[i][j]);
//初始化前缀数组
for (i = 1; i <= n; i++)
for (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
", s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]);
}
return 0;
}
