前缀和与差分

0.核心代码

一维

a[i]=a[i-1]+diff[i];

s[i]=s[i-1]+a[i];

sum[l,r]= S[r]-S[l-1];

//区间a[l,r]都加x：
a[l]+=x;
a[r+1]+=-x;

二维

s[i][j]=a[i][j]+s[i][j-1]+s[i-1][j-1]-s[i-1][j-1];//前缀和

d[i][j]=a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1];//求差分数组

sum[i1j1,i2j2]=s[i2][j2]-s[i1-1][j2]-s[i2][j1-1]+s[i1-1][j1-1]//求矩阵区间的总和.i1j1为矩阵左上角的点，i2j2位矩阵右下角的点

1.前缀和定义

image-20220117153015275

  • 对于q次询问
  • 先把s[i]求出，随后求sum[l,r]，就可以降低时间复杂度。一次询问复杂度为O(1)。总复杂度成为O(n)
  • 若用遍历，每次询问sum[l,r]的复杂度为O(n).总共则是O(q*n)

2.差分

image-20220117165258915

  • 问题：
    对于一个数组a的一个区间[L,R]，要求全部加x。
    • 一般方法：遍历数组加上x。单次的复杂度为O(n)，总为O(mn),若n和m过大就会超时。
    • 采用==差分法==：对这个数组的差分数组diff[]。对diff[L]+x，对diff[R+1]-x，再对该差分数组进行前缀和运算。//或者a[i]=a[i-1]+diff[i] 便可以求出加完之后的数组。

多次区间修改也是一样。

  • 差分数组的由来
    差分数组是原数组前缀和的逆运算，即a[i]-a[i-1]=diff[i]

    image-20220117170507308

  • 一个点的值就是会影响它的差分数组的前缀和

  • 差分数组的前缀和=原数组

  • 直接用差分数组b[n]求a[n]的前缀和image-20220119003537519

3.扩展到二维

  • 定义

image-20220117160941693

也可以是a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+a[i][j]直接将原数组代替

求红色矩阵，容斥原理：黑-绿-绿+蓝

image-20220120225815197

  • 二维差分

image-20220117215558796

定理：在红色处+x，右下角都会+c

推导：想在一个区间+c

image-20220117220306667

  • 例题

image-20220120154019142

  • 题解

image-20220120154320375

4题目

1.洛谷P1387 最大正方形

image-20220120230043224

  • 思路

采用暴力+前缀和

从大到小的边长遍历，并遍历数组的各个边长的矩阵的sum是否为边长^2

  • 题解
#include <iostream>
using namespace std;
#include <cmath>
#include <cstring>
#define MIN(x,y) ((x)<(y)?(x):(y))
int main() {
	int n,m;
	cin>>n>>m;
	int a[n+1][m+1];
	memset(a,0,sizeof(a));
	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]+a[i-1][j]+a[i][j-1]-a[i-1][j-1];
		}
	}
	
	int max=0;
	bool flag=false;
	for (int l=MIN(m, n); l>1; l--) {
		for (int i=l-1;i<=n ; i++) {
			for (int j=l-1; j<=m; j++) {
				int s=pow(l, 2);
				int o=a[i][j]-a[i][j-l]-a[i-l][j]+a[i-l][j-l];//计算矩阵区域的值的总和
				if (s==o) {
					max=l;
					flag=true;
					break;
				}
			}
			if (flag==true) {
				break;
			}
		}
		if (flag==true) {
			break;
		}
	}
	if (flag==false) {
		cout<<1<<endl;
	}else {
		cout<<max<<endl;
	}
}