labuladong: 论那些小而美的算法技巧：差分数组
一、差分配列什么时候使用？ 我想很多人都遇到过这样的问题：
如果设原始数组的长度为n，查询次数为m，
确保每次查询指定区间[l，r]和整数k时，原始数组在[l，r]之间的元素同时增加/减少k
输出最终数组
num [ 8，2，6，3，1 ] m=2
1 3 1
0 2 3
注：
首次咨询num=8 3 7 4 1
第二次查询num=11 6 10 4 1
最终num=11 6 10 4 1
当然，如果对每个查询遍历区间[l，r]进行修改，结果一定是正确的
但是，笔试和做题时，如果数据大而苛刻，往往会超时，时间复杂度为o(Mn )
二、什么是差配列？ 在这种情况下为差分数组 ： 主要适用场景是频繁对原始数组的某个区间的元素进行增减。
1、首先构造差分数组 diff，diff [ i ]=num [ i ] - num [ i - 1 ]
int[] diff=new int[nums.length]； //差分配序列diff[0]=nums[0]； for(intI=1； i nums.length； I ) { diff[i]=nums[i] - nums[i - 1]； }
通过该diff差分配列，可以反推原始数组nums。 代码逻辑如下：
int[] res=new int[diff.length]； //差分配序列到结果序列res[0]=diff[0]； for(intI=1； i diff.length； I({RES[I]=RES[I-1]diff[I]； ) 2、这样构建差分配列diff的话，为快速进行区间增减的操作。 如果想在区间 [ i , j ]的元素中添加3，只需将其设为3358www.Sina.com/，然后再设为http://www.som/即可
原理很简单，diff[ i ] += 3，diff[ j + 1 ] -= 3
如果花o(1)的时间修改diff数组，就等于修改了nums的整个区间。 多次修改diff，然后在diff数组中反向按，可以得到nums修改后的结果。
class Difference { //差分配列private int[] diff； 公共差异(int [ ] nums ) { assert nums.length 0； diff=new int[nums.length]； //差分配序列diff[0]=nums[0]； for(intI=1； i nums.length； I ) { diff[i]=nums[i] - nums[i - 1]； }/*闭区间[i，j]中val (也可以是负数) /公共语音增量(int j，int j，int val ) (diff ) I ) val； if(j1diff.Length ) { diff[j 1] -=val； }公共int [ ] result ((int ) ) RES=newint[diff.length]； //差分配序列到结果序列res[0]=diff[0]； for(intI=1； i diff.length； I({RES[I]=RES[I-1]diff[I]； }返回RES； }