假设某一数组d经常做在某一段区间[a,b]内统一进行加减的操作，由于每次进行操作都需要从a循环遍历到b,时间开销较大,所以可以采用差分数组来解决此类问题.
设数组d[]={8,1,3,6,5,4,2}
当需要在区间[0,3]上统一加3时,不采用循环的方式,而是新创建一数组c,初始每个下标上的值均为0,则:
在c[0]上+3变成3,在c[3+1]上-3变成-3;
此时,c数组:3,0,0,0,-3,0,0;
同理,当需要在[2,5]上统一加4时,让c[2]+4=4,c[5+1]-4=-4,此时,c数组
3,0,4,0,-3,0,-4;
再当需要在[1-6]上-2时,由于6已经是数组最后一个元素,所以只需要在c[1]上-2即可,(c[6+1]不存在)
此时c数组:3,-2,4,0,-3,0,-4
之后,求出c数组的前缀和数组:
3,1,5,5,2,2,-2;
将原始数组d中的每个元素分别加上前缀和数组中的每一个元素,产生一个新的数组
a:[11,2,8,11,7,6,0],该数组即为最终执行结果.
假设进行m次在数组区间进行统一加减的操作,暴力算法的则时间复杂度mO(b-a),
此种算法由于每次只在c数组上改变两个元素,所以是m2次,又因最后需要算前缀和数组,以及前缀和数组与初始数组相加,是2O(N),所以优化后一共的时间复杂度是2(m+O(N))
