差分算法是一种在计算机科学中常用的算法，特别是在处理序列数据时，它可以帮助我们快速计算出序列中相邻元素的差值。时间复杂度可以达到O(1)，在C++中实现差分算法不仅可以提高程序的效率，还可以简化代码的复杂度。本文将详细介绍差分算法的原理、C++实现方法以及算法例题。 

上一篇博客一篇带你速通前缀和算法（C/C++）我们介绍了前缀和算法，这一篇文章就与前缀和算法相反为差分算法。

差分算法的核心思想是利用已有的数据序列，通过计算相邻元素之间的差值来生成一个新的序列。对于一个给定的序列 a=[a1​,a2​,...,an​]，其差分序列 d 可以表示为：d[i]=a[i]−a[i-1]。差分数组长度一般为原定序列长度+1，即：len=n+1。其中，d[0] 通常被定义为0，或者根据具体应用场景进行特殊处理。我们设原数组序列为a=[3,1,5,4,2]，下标从1开始，那么差分数组可以由d[i]=a[i]−a[i-1]求得，如下图所示。

​

一维差分在修改区间时效率非常高，时间复杂度可以达到 O(1)，我们通过对差分数组的修改以达到修改原数组的目的，那么如何修改差分数组，比如在数组a的[l,r]区间上的数统一+c，转化为差分数组为d[l]+c，d[r+1]-c，这样我们再利用前缀和还原便可以得到原数组修改后的值。在还原时，只需要将前i位差分数组相加便可以得到原数组，比如还原第三位，a[3]=d[1]+d[2]+d[3]，便可以还原其值，其还原的第n+1位一定是0。

​

我们设原数组序列为 a=[3,1,5,4,2]，设d为差分数组，在[2,4]区间上的值统一+2，下面我们将模拟实现。

​

我们需要在[2,4]区间上的值统一+2，那么转换为差分数组d[l]+c，d[r+1]-c==d[2]+2，d[4+1]-2。我们代入到过程实现一下。

 原数组序列为 a=[3,1,5,4,2]，在[2,4]区间上的值统一+2，我们将得到a=[3,3,7,6,2]，与差分还原的来是一样的。

前面我们讲述的是一维差分，其数组为一维的，其模型可以抽象为线性的。那么有些时候需要我们使用二维差分，当题目出现矩阵时，说明就涉及到了二维差分，其模型可以抽象为矩阵，二维差分稍微比一维差分难一点，主要是在处理区间更新时。我们设d[i][j]为（1，1）点到（i，j）点的差分子矩阵（1<=x<=i,1<=y<=j）,此时我们设a[i][j]=Σd[i][j]（1<=x<=i,1<=y<=j），即a[i][j]=差分矩阵的和。

当我们需要构造差分数组实现修改区间的值时，此时的递推关系式不再是跟一维差分相同，由于是二维的，所以转化为在一个矩阵上+c，在一个矩阵上-c，那么如何确定这两个矩阵。假设我们在（x1,y1）->(x2,y2)这个矩阵统一加C，那么转化为差分矩阵的操作为

d[x1][y1]+C
d[x1][y2+1]-C
d[x2+1][y1]-C
d[x2+1][y2+1]+C
 
//上面操作等价于
for(int i=x1;i<=x2;i++)
  for(int j=y1;j<=y2;j++)
    a[i][j]+=C;

 在构造差分矩阵时，可以先初始化一个差分矩阵都为0，把自己的点，（x,y）->(x,y)插入到差分矩阵中，代码如下：

void insert(int x1, int y1, int x2, int y2, int c)//构造差分矩阵
{
    b[x1][y1] += c;
    b[x2 + 1][y1] -= c;
    b[x1][y2 +1] -= c;
    b[x2 +1][y2+1] +=c;
}

d[x1][y1]+C相当于原矩阵A矩阵（黄色）每个值都+C

d[x2+1][y2+1]+C相当于整个矩阵A+B+C+D矩阵每个值都+C

此时A矩阵+2C,B矩阵+C,C矩阵+C，D矩阵+C,我们再设法把不需要的减掉。

d[x1][y2+1]-C相当于A+B矩阵（黄色+绿色）都-C

此时A矩阵+C,B矩阵+0,C矩阵+C，D矩阵+C,我们再设法把不需要的减掉。

d[x2+1][y1]-C相当于A+C矩阵（黄色+蓝色）都-C

此时A矩阵+0,B矩阵+0,C矩阵+0,D矩阵+C,达到了我们所需要的（x1,y1）到（x2,y2）加C的目的。

最后就是还原其值，利用前缀和的思想，如上图所示，要求（1，1）->（x2,y2）的值，那么可以转化为矩阵（1，1）->（x2,y2-1）与（1，1）->（x2-1,y2）的和减去（1，1）->（x2-1,y2-1）矩阵的值，最后再加上自身值d[x2][y2]。其递归式为d[i][j] += d[i - 1][j] + d[i][j - 1] - d[i - 1][j - 1]。

for (int i = 1; i <= n; i++)//二维前缀和还原
    {
        for (int j = 1; j <= m; j++)
        {
            d[i][j] += d[i - 1][j] + d[i][j - 1] - d[i - 1][j - 1];
        }
    }

#include<iostream>
using namespace std;
 
const int N =1010;
 
int a[N][N],d[N][N];
int n,q;
 
void insert(int x1, int y1, int x2, int y2, int c)
{
    d[x1][y1] += c;
    d[x2 + 1][y1] -= c;
    d[x1][y2 +1] -= c;
    d[x2 +1][y2+1] +=c;
}
 
int main()
{
    scanf("%d%d", &n,&q);
    for(int i = 1;i <= n; i++){
    	for(int j = 1;j <= n; j++){
    		cin >> a[i][j];
    		insert(i, j, i, j, a[i][j]);
		}
	}
    while( q-- )
    {
        int x1, x2, y1, y2,c;
        cin >> x1 >> y1>> x2 >> y2 >> c ;
        insert(x1 ,y1, x2, y2, c);//修改区间
    }
    
    //求前缀和
    for(int i = 1; i<=n; i++){
    	for(int j = 1; j<=n; j++){
        	d[i][j] += d[i][j-1] + d[i-1][j] - d[i-1][j-1];
        printf("%d ", d[i][j]);
		}
		cout<<endl;
	}
    return 0;
}

Farmer John 的 N 头奶牛对他们牛棚的室温非常挑剔。

有些奶牛喜欢温度低一些，而有些奶牛则喜欢温度高一些。

Farmer John 的牛棚包含一排 N 个牛栏，编号为 1…N，每个牛栏里有一头牛。

第 i 头奶牛希望她的牛栏中的温度是 pi，而现在她的牛栏中的温度是 ti。

为了确保每头奶牛都感到舒适，Farmer John 安装了一个新的空调系统。

该系统进行控制的方式非常有趣，他可以向系统发送命令，告诉它将一组连续的牛栏内的温度升高或降低 1 个单位——例如「将牛栏 5…8 的温度升高 1 个单位」。

一组连续的牛栏最短可以仅包含一个牛栏。

请帮助 Farmer John 求出他需要向新的空调系统发送的命令的最小数量，使得每头奶牛的牛栏都处于其中的奶牛的理想温度。

输入的第一行包含 N。

下一行包含 N 个非负整数 p1…pN，用空格分隔。

最后一行包含 N 个非负整数 t1…tN。

输出一个整数，为 Farmer John 需要使用的最小指令数量。

1≤N≤10^5

0≤pi,ti≤10000

5

1 5 3 3 4

1 2 2 2 1

5

一组最优的 Farmer John 可以使用的指令如下：

初始温度     ：1 2 2 2 1

升高牛棚 2..5：1 3 3 3 2

升高牛棚 2..5：1 4 4 4 3

升高牛棚 2..5：1 5 5 5 4

降低牛棚 3..4：1 5 4 4 4

降低牛棚 3..4：1 5 3 3 4

一个数组转化到另一个数组，我们可以考虑利用差分，快速解决，在一个区间上所有的数加上一个数k或者减去一个数k，我们可以等价转化为差分数组在区间两端一个+k一个-k。题目中起始数组到目标数组，我们可以把这两个数组做差值，然后差值数组变为差分数组，等价为转化到全零数组。差分数组每个值加和必为0（此题必有解），因为我们每次只相当于在差分数组两个值上加减，一个加一个减，要到达0数组，那肯定小于0的每次+1，直到为0，大于0的每次-1，直到为0。

p数组：   1 5 3 3 4
t数组：   1 2 2 2 1
差值数组：0 3 1 1 3
差分数组：0 3 -2 0 2 -3
第一次：  0 2 -1 0 2 -3
第二次：  0 1  0 0 2 -3
第三次：  0 0  0 0 2 -2
第四次：  0 0  0 0 1 -1
第五次：  0 0  0 0 0  0
所以只需要统计大于0或者小于0的值即可

#include<iostream>
using namespace std;
const int N=1e5+5;
int n,ans;
int p[N],t[N];//p数组既作为p数组又作为差分数组
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>p[i];
	}
	for(int i=1;i<=n;i++){
		cin>>t[i];
		p[i]-=t[i];
	}
	//差分p[i]=p[i]-p[i-1],差分数组边界p[1]=p[1],p[n+1]=-p[n]
	for(int i=n+1;i>=1;i--){//因为i要先于i-1更新，所以逆序遍历
		p[i]-=p[i-1];
	}
	for(int i=1;i<=n+1;i++){//只要遍历大于0或者小于零的p[i]累加即可
		if(p[i]>0){
			ans+=p[i];
		}
	}
	cout<<ans<<endl;
	return 0;
}

某公司养有观赏花，这些花十分娇贵，每天都需要且仅需要浇水一次。

如果某一天没给花浇水或者给花浇水超过一次，花就会在那一天死亡。

公司即将迎来 n 天假期，编号 1∼n。

为了让花能够活过整个假期，公司领导安排了 m 个人（编号 1∼m）来公司浇花，其中第 i 个人在第 [ai,bi] 天每天来公司浇一次花。

领导是按照时间顺序安排的浇花任务，保证了对于 1≤i≤m−1，均满足：bi≤ai+1。

给定领导的具体安排，请你判断，花能否活过整个假期，如果不能，请你输出它是在第几天死的，以及那一天的具体浇水次数。

第一行包含两个整数 n,m。

接下来 m 行，每行包含两个整数 ai,bi。

输出一行结果。

如果花能活过整个假期，则输出 OK。

如果花不能活过整个假期，则输出两个整数 x,y，表示花是在第 x 天死的，这一天花被浇了 y 次水。

前 4 个测试点满足 1≤n,m≤10。

所有测试点满足 1≤n,m≤10^5，1≤ai≤bi≤n。

10 5

1 2

3 3

4 6

7 7

8 10

OK

10 5

1 2

2 3

4 5

7 8

9 10

2 2

10 5

1 2

3 3

5 7

7 7

7 10

4 0

这道题其实一眼看上去是区间合并问题，这里我们讲解的差分算法，那么我们就用差分解决此题。员工在一个区间内浇水那么就可以视为区间修改，可以构造差分数组快速解决，这道题还一个条件就是花不能多浇水，这个实现也可以在差分数组之中，我们可以利用前缀和还原差分数组得到此朵花被浇了几次水，进而判断此花是否存活。

#include<iostream>
 
using namespace std;
const int N = 1e5 + 5;
 
int n,m;
int b[N];
 
int main(){
    cin >> n >> m;
    while(m--){
        int l,r;
        cin >> l >> r;
        b[l]++;//构造差分数组
        b[r + 1]--;
    }
    for(int i = 1;i <= n;i++){
        b[i] = b[i] + b[i - 1];//前缀和还原
        if(b[i] > 1 || b[i] < 1) {//超过一次浇水或者一次也没有浇水
            cout << i << ' ' << b[i] << endl;
            return 0;
        }
    }
    cout << "OK" << endl;
    return 0;
}

在大学期间，经常需要租借教室。

大到院系举办活动，小到学习小组自习讨论，都需要向学校申请借教室。

教室的大小功能不同，借教室人的身份不同，借教室的手续也不一样。 

面对海量租借教室的信息，我们自然希望编程解决这个问题。

我们需要处理接下来 n 天的借教室信息，其中第 i 天学校有 ri 个教室可供租借。

共有 m 份订单，每份订单用三个正整数描述，分别为 dj,sj,tj，表示某租借者需要从第 sj 天到第 tj 天租借教室（包括第 sj 天和第 tj 天），每天需要租借 dj 个教室。 

我们假定，租借者对教室的大小、地点没有要求。

即对于每份订单，我们只需要每天提供 dj 个教室，而它们具体是哪些教室，每天是否是相同的教室则不用考虑。 

借教室的原则是先到先得，也就是说我们要按照订单的先后顺序依次为每份订单分配教室。

如果在分配的过程中遇到一份订单无法完全满足，则需要停止教室的分配，通知当前申请人修改订单。

这里的无法满足指从第 sj 天到第 tj 天中有至少一天剩余的教室数量不足 dj 个。 

现在我们需要知道，是否会有订单无法完全满足。

如果有，需要通知哪一个申请人修改订单。

第一行包含两个正整数 n,m，表示天数和订单的数量。 

第二行包含 n 个正整数，其中第 i 个数为 ri，表示第 i 天可用于租借的教室数量。 

接下来有 m 行，每行包含三个正整数 dj,sj,tj，表示租借的数量，租借开始、结束分别在第几天。 

每行相邻的两个数之间均用一个空格隔开。

天数与订单均用从 1 开始的整数编号。

如果所有订单均可满足，则输出只有一行，包含一个整数 0。

否则（订单无法完全满足）输出两行，第一行输出一个负整数 −1，第二行输出需要修改订单的申请人编号。

1≤n,m≤10^6

0≤ri,dj≤10^9

1≤sj≤tj≤n

4 3

2 5 4 3

2 1 3

3 2 4

4 2 4

-1

2

此题可用差分+二分或者线段树来解，由于博主能力限制这里会由易懂的差分+二分来讲解。这道题第一感觉应该就是差分了吧，修改区间的值，用差分效率更高一点。我们可以把申请人的需要转化成差分数组，利用前缀和还原，判断i个教室是否满足。如果我们只依靠差分是解决不了此题的，只利用差分时间复杂度为O(nm),大约10^12，肯定会超时，那么我们可以考虑把内层循环利用二分优化掉，具体咋优化呢，我们有了一个申请人编号的差分数组，从第一位申请单到最后一个申请单，越在前面的越容易借到教室，说明教室剩余够多，越到后面剩余可借教室会减少，因为会被前面的申请借去，那就说明第一个不满足的编号越往后概率越高，这样是不是感觉像是一个有序的序列，从头到尾，能满足的概率是由大到小的。那么我们利用二分去查到最后一个能满足的订单，+1即为不能满足的订单，上代码。

#include<iostream>
#include<cstring>
using namespace std;
typedef long long LL;
const int N=1e6+5;
int n,m;
LL r[N],d[N],s[N],t[N],c[N];
bool cheak(int mid){//判断第mid个申请是否可以满足
	memset(c,0,sizeof(c));//每次都会有判断，防止上次的数据影响本次的判断
	for(int i=1;i<=mid;i++){//采用申请人由0到差分数组，所以直接差分操作即可
		c[s[i]]+=d[i];
		c[t[i]+1]-=d[i];
	}
	int ans=0;
	for(int i=1;i<=n;i++){//求前缀和，即还原数组
		c[i]+=c[i-1];
		if(c[i]>r[i]){//如果需要的教室大于所能提供的教室，则返回false
			return false;
		}
	}
	return true;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>r[i];
	}
	for(int i=1;i<=m;i++){
		cin>>d[i]>>s[i]>>t[i];
	}
	int l=0,r=m;
	while(l<r){//实行二分查找最大能满足的申请人编号
		int mid=l+r+1>>1;//向上取整
		if(cheak(mid))l=mid;
		else r=mid-1;
	}
	if(r==m){//如果最大满足的编号等于m，说明所有订单均可满足
		cout<<0<<endl;
	}else{
		cout<<-1<<endl<<r+1<<endl;//前面定义的为能满足的最大编号，r+1即为第一个不能满足的编号
	}
	return 0;
}

由此篇可见差分还是比较重要的，区间修改算法的效率也是非常高的，在算法竞赛中比较重要，希望对大家有所帮助，文章有错误的地方，恳请各位大佬指出。执笔至此，感触彼多，全文将至，落笔为终，感谢大家的支持。