前缀和和差分数组

首先知道前缀和概念是什么，假设有一个数列\(A\)，他的前缀和数列为\(S\)。

那么很容易就能得到前缀和公式：\(S[i]=\displaystyle\sum^i_{j=1}A[j]\)

如果要求区间\([l,r]\)的和呢？

答案也是很简单：\(sum[l,r]=S[r]-S[l-1]\)

所以前缀和用来求区间和问题非常有用。

如果一道题要让你对多个不同区间\([l,r]\)进行加减操作，再让你输出某一段区间的和呢？如果直接暴力大概率TLE，所以接下来要引入差分数组的概念：

设原数组为\(A[i]\)，差分数组为\(B[i]\)，则：

差分数组的性质：

• 如果对区间\([l,r]\)进行修改，对差分数组的修改就只有\(，B[l]，B[r+1]\)（\(B[l]\)加上修改值，\(B[r+1]\)减去修改值）
• \(A[i]=\displaystyle\sum^i_{j=1}B[j]\) （可以通过\(B[i]=A[i]-A[i-1]\)来证明）
• \(S[x]=\displaystyle\sum^x_{i=1}A[i]=\displaystyle\sum^x_{i=1}\displaystyle\sum^i_{j=1}B[j]=\displaystyle\sum^x_{i=1}(x-i+1)*B[i]\)

所以可以通过差分数组来计算前缀和。

下面上道例题：

有n个数。

m个操作,每一次操作，将x~y区间的所有数增加z；

最后有q个询问，每一次询问求出x~y的区间和。

直接用暴力前缀和很明显没办法快速计算，所以得用到差分数组。

设\(A\)为原数组。

先求出差分数组\(B[i]=A[i]-A[i-1]\)

再根据\(m\)个操作修改\(B[i]\)

• 设每一项\(A[i]=f[i]=f[i-1]+B[i]\)
• 则前缀和\(S[i]=S[i-1]+f[i]\)

（上面两步为差分数组性质3倒数第二步，也可以直接通过差分数组性质3最后一步直接计算）

最后\(sum[x,y]=sum[y]-sum[x-1]\)

接下来是一道二维的前缀和题目，也是运用了一点DP

最大子矩阵

从\(dp[i,j]\)保存的是\(dp[1,1]\)到\(dp[i,j]\)的矩形内的所有元素的和，即前缀和。

#include<bits/stdc++.h>
using namespace std;

int dp[1005][1005];

int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		memset(dp, 0, sizeof(dp));
		int m, n, x, y, mmax = 0;
		cin >> m >> n >> x >> y;
		for(int i=1;i<=m;i++)
			for (int j = 1; j <= n; j++)
			{
				cin >> dp[i][j];
				dp[i][j] += dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1];//二维数组前缀和
				if (i >= x && j >= y)
					mmax = max(mmax, dp[i][j] - dp[i - x][j] - dp[i][j - y] + dp[i - x][j - y]);//求x*y内元素的最大和
			}
		cout << mmax << endl;
	}
	return 0;
}