差分算法

差分是一种常见的算法，用于快速修改数组中某一段区间的值。其基本思想就是预处理出数组的差分数组，然后修改区间时，只需要修改两个位置的值，即可快速完成区间修改。最后再通过差分数组求出原数组。差分算法在区间加、区间求和等问题中都有广泛的应用。

算法思想

• 在原序列的基础上构造差分数组$d[]$，其中$d[i]$表示序列中相邻两个元素之间的差值，即$d[i]=A[i]-A[i-1]$。例如：对于序列$A=(0,0,0,0,0,0,0,0,0,0)$的差分数组 d [ ] = { 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 } d[]=\{0,0,0,0,0,0,0,0,0,0\} d[]={0,0,0,0,0,0,0,0,0,0}
  

• 在修改区间时，只需要更新差分数组两个位置上的值，即可快速完成修改。例如：给区间$[L,R]$的元素加上$k$，那么只需要将差分数组$d[L]+=k$，$d[R+1]-=k$即可。例如：对序列$A$的区间$[2,5]$每个数增加$3$，则将差分数组$d[2]+=3,d[6]-=3$即可；对序列$A$的区间$[1,7]$每个数增加$2$，则将差分数组$d[1]+=2,d[8]-=2$即可；
  

• 最后，通过对差分数组计算前缀和来还原出更新之后的序列。
  

时间复杂度

前缀和算法的时间复杂度分为两部分：

• 对原序列的区间增加值：$O(1)$
• 对差分数组求前缀和：$O(n)$

代码模板

//构造差分数组
void add(int L, int R, int k) 
{d[L] += k;d[R + 1] -= k;
}
//对差分数组求前缀和，还原序列
for(int i = 1; i <= n; i ++)d[i] += d[i - 1];

真题演练

题目链接：山东CSP-J2022 入门组1

有一排树苗，编号依次是$0，1，2，...$。现有$n$个志愿者去给树苗浇水，第$i$个志愿者选定了一个区间$[a_i，b_i]$，表示第$i$个志愿者将$[a_i，b_i]$这一区间内的每一棵树都浇一次水。

如某个志愿者选择的浇水区间为$[4，9]$，表示他将给编号为$4，5，6，7，8，9$的树各浇水一次。

当所有的志愿者完成各自所选区间的浇水后，可能有些树苗被不同的志愿者浇力多次，也可能有的树苗一次也没被浇过水。

请你求出浇水最多的树苗被浇了多少次。

输入格式

第1行，一个整数$n$，表示志愿者的人数。

第2行到第$n+1$行，每行两个整数$a_{，}{b}_i（i=0，1，2，...n-1）$，表示志愿者i选择的浇水区间。

输出格式

输出1行，$1$个整数，表示浇水最多的树苗被浇水的次数。

样例输入

4
0 2
2 4
1 4
6 7

样例输出

3

提示

对于所有的数据：$n<10^5$，$0<a<b<10^6$。

解题思路

根据题目描述有$n$个志愿者去给树苗浇水，每个志愿者将$[a_i，b_i]$这一区间内的每一棵树都浇一次水，求浇水最多的树苗被浇了多少次。那么：

• 可以用数组$d[]$表示每个位置的浇水次数，$d[]$初始化为$0$.
• 每次对区间$[L,R]$浇水时，将差分数组$d[L]+=1,d[R+1]-=1$
• 最后对差分数组求前缀和得到每棵树苗的浇水次数，并求出其中的最大值。

代码实现

#include <iostream>
using namespace std;
const int N = 1e6 + 10;
int d[N]; //差分数组
int main()
{int n, m = 0;scanf("%d", &n);for(int i = 1; i <= n; i ++){int L, R;scanf("%d%d", &L, &R);d[L] += 1, d[R + 1] -= 1;m = max(m, R);}int ans = 0;for(int i = 0; i <= m; i ++){if(i > 0) d[i] += d[i - 1];ans = max(ans, d[i]);}cout << ans << endl;
}

总结

• 差分算法可以快速修改序列中某一段连续区间的值。过程如下：
  • 在原序列的基础上构造差分数组
  • 给区间$[L,R]$的元素加上$k$，那么只需要将差分数组$d[L]+=k$，$d[R+1]-=k$
  • 对差分数组计算前缀和来还原出更新之后的序列。
• 除此之外，差分的思想还可以扩展到二位数组中。