差分数组
什么是差分数组？
差分数组：差分数组就是原始数组相邻元素之间的差。
其实差分数组是一个 辅助数组，从侧面来表示给定某一数组的变化，一般用来对数组进行区间修改的操作。
比如说对于上文的数组，将区间【1，4】的数值全部加上3， 其实当原始数组中元素同时加上或者减掉某个数，那么他们的差分数组其实是不会变化的，如下图所示：
对区间 [1, 4] 的元素都进行加3操作，差分数组中改变的只是 d[1] 和 d[5]，而 d[2] d[3] d[4] 都没变。
把上一步得到的数组当成原数组，再将区间【3，5】的数值全部减去5，结果如下：
总结：当对一数组的某个区间进行增减某个值时，其差分数组对应的区间左端点的值会同步变化，而他的右端点的后一个值则会相反变化。
参考博文：差分数组
差分数组的作用
差分数组的作用就是 求多次进行区间修改后的数组。构造出差分数组，就可以快速进行区间增减了。花费O(1)的时间修改 diff 数组，就相当于给原数组的整个区间做了修改。
注意 ：只能是区间元素同时增加或减少相同的数的情况才能用。
编码实现
通过原数组求出差分数组：
int[] diff = new int[nums.length];
// 根据原数组构造差分数组
diff[0] = nums[0];
for(int i = 1; i < nums.length; ++i) {
diff[i] = nums[i] - nums[i - 1];
}
通过差分数组得到结果数组：
int[] res = new int[diff.length];
// 通过差分数组得到结果数组
res[0] = diff[0];
for(int i = 1; i < diff.length; ++i) {
res[i] = res[i - 1] + diff[i];
}
return res;
//-------------其实直接在diff上操作即可得到结果数组----------------
for(int i = 1; i < diff.length; ++i) {
diff[i] += diff[i - 1];
}
return diff;
给区间 [i, j] 增加 val（可以是负数）：
// 直接操作 diff
diff[i] += val;
if(j + 1 < diff.length) {
diff[j + 1] -= val;
}
例子
lc-1109. 航班预订统计
* 给你输⼊⼀个⻓度为 n 的数组 nums，其中所有元素都是 0。再给你输⼊⼀个 bookings，⾥⾯是若⼲三元组(i,j,k)，
* 每个三元组的含义就是要求你给 nums 数组的闭区间 [i-1,j-1] 中所有元素都加上 k。请你返 回最后的 nums 数组是多少？
输入：bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5
输出：[10,55,45,25,25]
这个例子初始的原数组全为0，表示 n 个航班初始预定的座位数都为0。对原数组的某些区间有多次加操作，过程如下：
`txt
0 0 0 0 0
10 10
20 20
25 25 25 25
Original: https://www.cnblogs.com/afei688/p/16598099.html
Author: 阿飞的客栈
Title: 差分数组入门
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/616684/
转载文章受原作者版权保护。转载请注明原作者出处！