什么是差分
给出前缀和数组S[n], 让我们构造差分数组b[n], 满足条件S[i] = b[1] + b[2] + .... + b[i];
我们就称b[n]是前缀和数组的差分数组,S[n]是b[n]的前缀和;
也就是说 差分是前缀和的逆运算
作用
前缀和数组S[n]在某个区间[l,r]上加上c,我们现在只需要对差分数组中的两个数+c,-c就可以了;
很明显,在区间上操作时间复杂度是O(n),对两个数操作时间复杂度是O(1);O(n)–>O(1)
Java模板
1:构造差分数组公式:b[i] = S[i] - S[i-1]
2:给区间S[l, r]中的每个数加上c等价于 b[l] += c, b[r + 1] -= c
写代码的话只需要记住这两个公式就可以了
公式验证:
现在有两个数组:
前缀和数组S[n]:2,3,6,12,16
差分数组b[n]:2,1,3,6,4
前缀和公式: S[i] = S[i-1] + b[i]; (这个应该在上两节已经学过了)
公式1::b[i] = S[i] - S[i-1] 用于得到我们的差分数组
这个很好理解,S[i] = S[i-1] + b[i]; 转化一下就是b[i] = S[i] - S[i-1]
公式2:给区间S[l, r]中的每个数加上c等价于 b[l] += c, b[r + 1] -= c;
比如说:我们设l = 1; r = 2;c = 1;
S[n]就变成了 3,4,6,12,16
但是直接这么变时间复杂度是O(n),所以我们就转化一下,利用公式一计算出差分数组b[n],然后对差分数组中的两个数进行操作,就会简单很多;如下:
b[l] += c; 就是让左区间+c=2+1=3,相当于让S[l~n]都加上了c,很明显不是我们想要的;
b[r + 1] -= c; 让右区间的右一个数-c= 3 - 1 =2,相当于S[r+1,n]相当于没有变化
这样的话,就把区间固定在了S[l,r],以外的区间没有影响;
差分数组就变成了3,1,2,6,4
最后:再把差分数组转化为前缀和数组:3,4,6,12,16 可以看出来和上面的结果是一样的,说明是等价的
总结:思路 1:把前缀和数组S[n]转化为差分数组
2:对差分数组进行b[l] += c, b[r + 1] -= c;操作
3:把差分数组转化为操作后的前缀和数组
然后我们按照思路步骤实现代码就可以了
Java代码
import java.util.Scanner;
public class Main{
private static int N = 100010;
public static void main(String[] args){
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
int[] s = new int[N]; //初始化原数组a[]
for(int i = 1 ; i <= n ; i++) s[i] = in.nextInt();
int[] b = new int[N]; //1:初始化差分数组b[]
for(int i = 1 ; i <= n ; i++) b[i] = s[i] - s[i-1];
while(m-- > 0){ //2:在前缀和数组的[l,r]区间上加c 等价于 在差分数组上b[l] += c;b[r+1] -= c;
int l = in.nextInt();
int r = in.nextInt();
int c = in.nextInt();
b[l] += c;
b[r+1] -= c;
}
for(int i = 1 ; i <= n ; i++) b[i] = b[i-1] + b[i]; //3:把差分数组转化为为操作完后的前缀和数组
for(int i = 1 ; i <= n ; i++) System.out.print(b[i] + " ");
}
}
太秀了
zan!
zan!