1. 题目
2. 读题(需要重点注意的东西)
思路:二维前缀和,多用于求区间和,能将O(n)的时间复杂度转换为O(1);
关键代码在于
1. 求前缀和
- 求区间和:左上角的坐标为(x1,y1),右下角的坐标为(x2,y2),求此区间的和的公式为
3. 解法
---------------------------------------------------解法---------------------------------------------------
#include<iostream>
using namespace std;
const int N = 1010;
int s[N][N];
int main(){
int n , m, q;
cin >> n >> m >> q;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++)
scanf("%d",&s[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];
}
while(q--){
int x1,x2,y1,y2;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
cout << s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]<<endl;
}
return 0;
}
4. 可能有帮助的前置习题
5. 所用到的数据结构与算法思想
6. 总结
二维前缀和模板,主要应用于求区间和,推荐完全背下来