题目链接:【模板】二维前缀和_牛客题霸_牛客网
先举两个简单的例子,来帮大家理解题目,注意理解二维前缀和要先要一维前缀和的基础,不了解的可以看我上一篇博客。
若x1=1,y1=1, x2=3, y2 = 3,这是要查询下面这片区域的和:
若x1=3,y1=3, x2=6, y2 = 5,这是要查询下面这片区域的和:
暴力解法很简单,直接死算,必定超时,所以还是要构建我们的前缀和数组(dp),dp数组的构建方法绝不能是每个数据都死死的去加一遍,不然和暴力解法没什么区别,也会超时。
如何更高效地构造二维前缀和数组呢,之前构建一维前缀和数组时,我们可以很快用肉眼看出规律,但二维前缀和数组的构建方法需要我们画图,寻找新方法:
我们将原数组划分为4个部分,此时我们要求dp[i][j]的大小,其实就是整个图形的面积也就是A+B+C+D,A很好表示,A=dp[i-1][j-1],D就一个元素也很好表示,D=arr[i][j] ,可是B和C却不好表示,但是A+B和A+C我们却很好表示,A+B=dp[i-1][j],A+C=dp[i][j-1],如图:
所以我们就得出了我们的重要结论:
dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+arr[i][j]
通过这个表达式我们就能构建出二维前缀和数组了。
我们已经构建出了二维前缀和数组,那么如何使用它呢,如图,我们输入x1,y1,x2,y2后:
还是一样先划分为A,B,C,D 4个区域:
此时D为我们所求,还是根据刚才的思路,来换算:
D=A+B+C+D-(A+B+C)
A+B+C+D=dp[x2][y2]
B和C单独在一块不好求,就转化成A+B和A+C,如:
D=A+B+C+D-(A+B+C)=A+B+C+D-(A+B)-(A+C)+A=dp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]+dp[x1-1][y1-1]
所以的出重要结论:
D=dp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]+dp[x1-1][y1-1]
最后我们只需将x1,y1,x2,y2代入上式中就可以求得答案了。
C++:
#include <iostream>
#include<vector>
using namespace std;
int main() {
//读入数据
int n =0,m=0,q=0;
cin >> n >> m >> q;
vector<vector<int>> arr(n+1, vector<int>(m+1));
int i=1;
for(i=1;i<=n;i++)
{
int j=1;
for(j=1;j<=m;j++)
{
cin >> arr[i][j];
}
}
//处理dp数组
vector<vector<long long>> dp(n+1, vector<long long>(m+1));
for(i=1;i<=n;i++)
{
int j=1;
for(j=1;j<=m;j++)
{
dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+arr[i][j];
}
}
//开始使用dp数组进行q次查询
while(q--)
{
int x1=0,y1=0,x2=0,y2=0;
cin >> x1 >> y1 >> x2 >> y2;
cout << dp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]+dp[x1-1][y1-1] << endl;
}
return 0;
}