差分

• 0. 概述
• 1. 一维差分
• 2. 二维差分

复习一下前缀和吧：【C++算法模板】预处理算法：一维前缀和、二维前缀和总结，详解带例题-CSDN博客

0. 概述

• 差分的推导也比较简单，因此本博客重点在于知识点归纳而不在于证明

1. 一维差分

• 给定一个一维序列，定义它的差分序列 $b$ 为，计算差分序列的时间复杂度为 $O(n)$
  • $b[1]=a[1]\ (i=1)$
  • $b[i]=a[i]-a[i-1]\ (2<=i<=n)$
• 为原序列 $[l,r]$ 区间分别加上 $c$ 等价于：$b[l]+=c,\ b[r+1]-=c$，对差分序列 $b$ 做一维前缀和得到操作后的原序列，时间复杂度 $O(1)$

【例题】AcWing 797，链接：797. 差分 - AcWing题库

#include<bits/stdc++.h>
#define x first
#define y second

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;

// 题目描述: 

const int N=1e5+5;
int n,m;
int a[N],b[N]; // a:原序列,b:差分序列
int s[N]; // 对b求前缀和
int l,r,c;

int main() {
	cin>>n>>m;
	// 输入规模超过1e5,推荐使用scanf
	for(int i=1;i<=n;i++) {
		scanf("%d",&a[i]);	
		b[i]=a[i]-a[i-1]; // 前缀和和差分下标都从1开始,否则容易有边界问题
	}
	while(m--) {
		scanf("%d%d%d",&l,&r,&c);
		b[l]+=c;
		b[r+1]-=c;
	}
	// 用新数组s计算差分序列b的前缀和
	for(int i=1;i<=n;i++) {
		s[i]=s[i-1]+b[i];
		printf("%d ",s[i]);
	}
	cout<<endl;
	
	// 用累加的思想,在差分序列本身上做前缀和,节省空间
	for(int i=1;i<=n;i++) {
		b[i]+=b[i-1];
		printf("%d ",b[i]);
	}
	return 0;
}

2. 二维差分

• 在一维差分中我们对差分序列 $b$ 求前缀和可以得到原序列 $a$，由此可以看出差分是前缀和的逆运算

• 则我们可由二维前缀和计算公式轻松推导出二维差分序列的计算公式，时间复杂度 $O(n^2)$
  • 二维前缀和的计算公式 $s[i][j]=\sum_{i=1}^i\sum_{j=1}^ja[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j]$
  • 将 $a[i]$ 单独移至等号一边，对 $s$ 合并同类项，得到 $a[i][j]=s[i][j]-s[i-1][j]-s[i][j-1]+s[i-1][j-1]$
  • 由于 $b$ 的前缀和是 $a$，所以将 $a$ 替换成 $b$，将 $s$ 替换成 $a$，得到二位差分计算公式
  • $b[i][j]=a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1]$，其物理含义是：在下标 $[i][j]$ 位置上的差分等于原序列 $[i][j]$ 上的元素减去上边 $[i-1][j]$ 和左边 $[i][j-1]$ 上的元素并加上左上角 $[i-1][j-1]$ 的元素
• 对原序列 $a$ 区间 $(x_1,y_1)$ 到 $(x_2,y_2)$ 之间的元素加上 $c$，等价于其差分序列 $b$ 的点 $(x_1,y_1)$ 加 $c$，点 $(x_1,y_{2}+1)$ 减 $c$，点 $(x_2+1,y1)$ 减 $c$，点 $(x_2+1,y_2+1)$ 加 $c$，时间复杂度 $O(1)$，最后对差分序列 $b$ 求二维前缀和即可得到操作过后的原序列

【例题】AcWing 798，链接：798. 差分矩阵 - AcWing题库

#include<bits/stdc++.h>
#define x first
#define y second

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;

// 题目描述: 逐行差分和逐行求和的思路

const int N=1e3+5;
int n,m,k; // n:矩阵行数,m:矩阵列数,k:操作次数
int a[N][N];
int b[N][N]; // 差分矩阵

int s[N][N]; // 对b求二维前缀和得到操作后的原序列

int main() {
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=m;j++) {
			cin>>a[i][j];
			b[i][j]=a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1]; // 差分是前缀和的逆运算
		}
	}
	// 输出差分数组看一看
//	cout<<"输出差分数组:>\n";
//	for(int i=1;i<=n;i++,puts("")) {
//		for(int j=1;j<=m;j++) {
//			cout<<b[i][j]<<' ';
//		}
//	}
	int x1,y1,x2,y2,c;
	while(k--) {
		scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&c);
		b[x1][y1]+=c;
		b[x1][y2+1]-=c;
		b[x2+1][y1]-=c;
		b[x2+1][y2+1]+=c;
	}
	cout<<endl;
	// 求前缀和保存到s里面
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=m;j++) {
			s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+b[i][j];
			cout<<s[i][j]<<' ';
		}
		cout<<endl;
	}
	cout<<endl;
	// 直接在b本身上进行前缀和得到操作后的a
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=m;j++) {
			b[i][j]+=b[i-1][j]+b[i][j-1]-b[i-1][j-1];
			cout<<b[i][j]<<' ';
		}
		cout<<endl;
	}
	cout<<endl;

	return 0;
}

打赏