牛客每日一题之 二维前缀和

题目介绍：

题目链接：【模板】二维前缀和_牛客题霸_牛客网

 

先举两个简单的例子，来帮大家理解题目，注意理解二维前缀和要先要一维前缀和的基础，不了解的可以看我上一篇博客。

若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;
}