算法日记4：796. 子矩阵的和（二维前缀和）

题目链接：Acwing796. 子矩阵的和

一、题目

二、解题思路：

让我们来分解问题

2.1法一：暴力0(n²)

• 首先对于这个题目，我们最先想到的是暴力解法即两层for循环即可实现程序，但是此时我们的程序就过于复杂，
• 因为当多次询问时，我们每次询问都需要遍历两层for循环

2.2 法二：二维前缀和

1、首先，让我们来介绍一下二维前缀和的概念: prefix[i][j]表示从[1][1]到[i][j]的和

• 那么我们怎么求出prefix[i][j]数组呢？
• 这里可以类似一维前缀和，通过递推的方式求出prefix数组，如图所示
  
• 因此，我们可以总结出一个公式：

prefix[i][j]=p[i-1][j]+p[i][j-1]-p[i-1][j-1]+a[i][j]

• 此时，我们的前缀和数组就求解完毕了，接下来就是通过前缀和数组来进行查询操作

2、查询：通过前缀和的概念我们可以容易看出，计算从a[x1][y1]-->a[x2][y2]的图例：

因此我们可以总结公式：

a[x1][y1]-->a[x2][y2]=

p[x2][y2]-p[x2][y1-1]-p[x1-1][y2]+p[x1-1][y1-1]

三、题解：

#include<bits/stdc++.h>
using namespace std;const int N=2007;
int a[N][N];int calculate(int x1,int y1,int x2,int y2)	//询问
{return a[x2][y2]-a[x1-1][y2]-a[x2][y1-1]+a[x1-1][y1-1];
}int main()
{int n,m,q;cin>>n>>m>>q;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>a[i][j];}}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++)	//计算二维前缀和{a[i][j]=a[i][j-1]+a[i-1][j]-a[i-1][j-1]+a[i][j];}}while(q--){int x1,y1,x2,y2;cin>>x1>>y1>>x2>>y2;int res=calculate(x1,y1,x2,y2);cout<<res<<'\n';}return 0;
}