LeetCode - 差分数组技巧

What

差分数组技巧可以算是前缀和技巧的变体，其不统计从起止位置到目前元组的sum，而是统计当前元素相较于前一个元素的偏移量diff

例如一个数组 nums [1,2,3,4]
其对应的差分数组为 diff [1,1,1,1]

一般将差分数组的首个元素初始化为原数组中的数据。

对于一个nums，可以直接构造一个diff，同样的对于一个给定的diff数组，我们可以将其还原为nums。

Why

preSum用于快速计算区间和，而使用diff数组可以快速对区间中的值进行统一操作。

例如对于区间[i,j]我们想做一个 + 1 操作，那么只需要修改diff[i]+=1; diff[j+1]-=1，然后以更新后的diff[]还原为新的nums即可

具体来说，结合diff[]还原为nums[]的逻辑，diff[i] += 1 意味着给 nums[i..] 所有的元素都加了 1，然后 diff[j+1] -= 1 又意味着对于 nums[j+1..] 所有元素再减 1，这样综合起来，就对 nums[i..j] 中的所有元素都加 1 了

一些题目

L370 区间加法

直白的差分数组实现

L1109 航班预定

需要翻译的差分数组题目

L1094 拼车

需要翻译的差分数组题目