普通算法——二维前缀和
二维前缀和
题目链接：https://www.acwing.com/problem/content/798/
题目描述：
- 输入一个 n n n 行 m m m 列的整数矩阵，再输入 q q q 个询问，每个询问包含四个整数 ** x 1 , y 1 , x 2 , y 2 x1,y1,x2,y2 x1,y1,x2,y2 ， ， ，**表示一个子矩阵的左上角坐标和右下角坐标。
- 对于每个询问输出子矩阵中所有数的和。
思路：
- S [ i , j ] S[i,j] S[i,j] 即为图1红框中所有数的的和为： S [ i , j ] = S [ i , j − 1 ] + S [ i − 1 , j ] − S [ i − 1 , j − 1 ] + a [ i , j ] S[i,j]=S[i,j−1]+S[i−1,j]−S[i−1,j−1]+a[i,j] S[i,j]=S[i,j−1]+S[i−1,j]−S[i−1,j−1]+a[i,j]
- ( x 1 , y 1 ) , ( x 2 , y 2 ) (x1,y1),(x2,y2) (x1,y1),(x2,y2) 这一子矩阵中的所有数之和为： S [ x 2 , y 2 ] − S [ x 1 − 1 , y 2 ] − S [ x 2 , y 1 − 1 ] + S [ x 1 − 1 , y 1 − 1 ] S[x2,y2]−S[x1−1,y2]−S[x2,y1−1]+S[x1−1,y1−1] S[x2,y2]−S[x1−1,y2]−S[x2,y1−1]+S[x1−1,y1−1]
#include<iostream>
using namespace std;
const int N = 1010;
int n, m, q, a[N][N], sum[N][N], x1, x2, y1, y2;
int main(){
cin >> n >> m >> q;
for (int i = 1; i <= n; i++){
for (int j = 1; j <= m; j++){
cin >> a[i][j];
sum[i][j] = sum[i-1][j] + sum[i][j-1] + a[i][j] - sum[i-1][j-1];
}
}
while(q--){
cin >> x1 >> y1 >> x2 >> y2;
cout << sum[x2][y2] - sum[x1-1][y2] - sum[x2][y1-1] + sum[x1-1][y1-1] << endl;
}
return 0;
}
原文地址：https://blog.csdn.net/qq_73628657/article/details/144325830
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！