您的位置: 首页  >  文章  >  基础算法：差分讲解

基础算法：差分讲解

分类: 文章 • 2025-02-25 10:48:58

1.差分的基本概念：

如果有一数列 a[1],a[2],.…a[n]
且令 b[i]=a[i]-a[i-1],b[1]=a[1]

那么就有
a[i]=b[1]+b[2]+.…+b[i]
    =a[1]+a[2]-a[1]+a[3]-a[2]+.…+a[i]-a[i-1]
此时b数组称作a数组的差分数组
换句话来说a数组就是b数组的前缀和数组  例：
     原始数组a：9  3  6  2  6  8
     差分数组b：9 -6  3 -4  4  2
     可以看到a数组是b的前缀和

那么现在有一个任务：

在区间[left,right]上加一个常数c。
我们可以利用原数组就是差分数组的前缀和这个特性，来解决这个问题。显然可得出公式：b[left]+=c,b[right+1]−=c

同样如果通过以上问题让求某一区间的和，那么前缀和也同样能够完成，但是如果操作的次数过大
那么前缀和显然会超时，但是同样有解决的方式例如 树状数组，线段树。
相对于代码长度而言，使用差分的思想求解会变得异常简单。

下面看例题：
1.转自：https://blog.****.net/zsyz_ZZY/article/details/79918809
有n个数，m个操作,每一次操作，将x~y区间的所有数增加z；
最后有q个询问，每一次询问求出x~y的区间和。

分析：首先我们得到一个原数组a，然后
设d[i]=a[i]-a[i-1] (1<i≤n,d[1]=a[1])；//差分数组
设f[i]=f[i-1]+d[i] (1<i≤n,f[1]=d[1]=a[1])；
设sum[i]=sum[i-1]+f[i] (1<i≤n,sum[1]=f[1]=d[1]=a[1])。//区间求和

f数组就是最上面的b数组
基础算法：差分讲解

2.同样利用差分数组对某一区间的值进行修改，sum数组保存的就是前n项的和
只对区间两端的值进行修改，是因为每次的 f[i] 数组都包含着 f[i-1]+d[i],即如果在修改区间[left,right]内的话，从区间left开始以后的每一项都加上了修改值z，然后到最后一项right+1时就把z减掉
基础算法：差分讲解

代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<string>
#include<map>
#include<vector>
#include<set>
#include<deque>
#include<queue>
#include<stack>
#include<functional>
#include<cmath>
using namespace std;
const int N = 1010;
int a[N], sum[N],f[N];//即b数组
int main(){
	int n, m, q;
	cin >> n >> m>>q;//n个数，m个操作,q次询问
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	for (int i = n; i > 1; i--)//需要从大到小求
		a[i] -= a[i - 1];//此时a[i]数组表示的是a的差分数组
	for (int i = 1,x,y,k; i <= m; i++){
		cin >> x >> y >> k;//在区间[x,y]内的每个数加上k
		a[x] += k, a[y+1] -= k;//对区间两端的值进行修改
	}
	for (int i = 1; i <= n; i++){
		f[i] = f[i - 1] + a[i];//就跟b数组一样，f[i]表示a[i]
		sum[i] = sum[i - 1] + f[i];//自己理解为相当于前缀和
	}
	for (int i = 1,x,y; i <= q; i++){
		cin >> x >> y;
		cout << sum[y] - sum[x - 1] << endl;
	}
	return 0;
}

2.https://www.acwing.com/problem/content/description/102/

给定一个长度为 n 的数列 a1,a2,…,an每次可以选择一个区间 [l,r]，使下标在这个区间内的数都加一或者都减一。
求至少需要多少次操作才能使数列中的所有数都一样，并求出在保证最少次数的前提下，最终得到的数列可能有多少种。
输入格式
第一行输入正整数n。
接下来n行，每行输入一个整数，第i+1行的整数代表ai。
输出格式
第一行输出最少操作次数。
第二行输出最终能得到多少种结果。
数据范围
0<n≤105
0≤ai<2147483648

输入样例：
4
1
1
2
2
输出样例：
1
2
分析：题意是可以将连续一段数组的值加上1或者减去一，使得最后所有的数都相同，并且求出方案数。
我们假设b数组为序列a数组的差分数组,利用贪心的思想将b中的所有数字都变为零，因为b[i]=a[i]-a[i-1]，所以此时a序列肯定相等。

那么我们在找每次的修改区间[left，right]时，对于每个数无非就是负数++，正数–两种可能（因为要达到零,如果一开始为零的就不需要修改了）这样就是最少的次数。 因此先设正数和为pos,负数和为neg，那么最小的操作次数等于 min(pos,neg)+abs(neg-pos)=max(neg,pos) (即正负最大的一个）
然后最终序列可能有的情况为 abs(neg-pos)+1

建议自己写个序列理解一发

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=100010;
typedef long long ll;//这题可能爆ll
int a[N],b[N];
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    cin>>a[i];
    for(int i=n;i>1;i--)
    a[i]-=a[i-1];//相当于b数组，此时代表为差分数组
    ll pos=0,neg=0;//分别代表正负差分数组的和
    for(int i=2;i<=n;i++){
        if(a[i]>0) pos+=a[i];//差分数组中正项的和
        else neg-=a[i];//负项
    }
    cout<<max(pos,neg)<<endl;
    cout<<abs(pos-neg)+1<<endl;
    return 0;
}

3.https://www.acwing.com/problem/content/103/

最高的牛
有 N头牛站成一行，被编队为1、2、3…N，每头牛的身高都为整数。
当且仅当两头牛中间的牛身高都比它们矮时，两头牛方可看到对方。
现在，我们只知道其中最高的牛是第 P头，它的身高是 H，剩余牛的身高未知。但是，我们还知道这群牛之中存在这M对关系，每对关系都指明了某两头牛 A和 B可以相互看见。求每头牛的身高的最大可能值是多少。
输入格式
第一行输入整数N,P,H,M，数据用空格隔开。接下来M行，每行输出两个整数A和 B，代表牛 A和牛 B可以相互看见，数据用空格隔开。

输出格式
一共输出 N行数据，每行输出一个整数。第 i行输出的整数代表第 i头牛可能的最大身高。
数据范围
1≤N≤10000,1≤H≤1000000,1≤A,B≤10000,0≤M≤10000
输入样例：
9 3 5 5
1 3
5 3
4 3
3 7
9 8
输出样例：
5 4 5 3 4 4 5 5 5
注意：
此题中给出的关系对可能存在重复

基础算法：差分讲解
分析：我们先假设最两端的牛的高度都为最大值h那么对于下面的m条操作如果区间[left,right]的牛可以相互看见，那么说明在[left,right]区间的牛的高度只需要比两端最小的高度小1,并且我们需要set来判重。

另外此题只会出现嵌套关系，但那不可能出现重叠,因为有A，B关系可以推出C<B 但由C，D可以得到C>B,矛盾
基础算法：差分讲解
代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<string>
#include<map>
#include<vector>
#include<set>
#include<deque>
#include<queue>
#include<stack>
#include<functional>
#include<cmath>
using namespace std;
const int N = 10010;
int height[N];
set<pair<int, int> >st;//判重
int main(){
	int n, m, p, h;
	cin >> n >> p >> h >> m;
	height[1] = h;//设第一头牛的高度为h
	for (int i = 1, x, y; i <= n; i++){
		cin >> x >> y;
		if (x>y) swap(x, y);//保持x<y
		if (!st.count({ x, y })){//如果不存在
			st.insert({ x, y });//加入
			height[x + 1]--;//[x,y]中间的牛的高度比两端的低1就行了
			height[y]++;
		}
	}
	for (int i = 1; i <= n; i++){
		height[i] += height[i - 1];//每头牛的高度等于等于前一头牛减去自己比他少的height[i],画图理解
		cout << height[i] << endl;
	}
	return 0;
}

相关推荐