差分数组

差分数组是与前缀和数组所对应的一种逆操作，类似于求导和积分，也就是说，对差分数组求前缀和，可以得到原数组，同样的，对前缀和数组求差分，也可以得到原数组。^[1]

1. 差分数组的定义

给定数组 a[i]，差分数组 d[i] 定义为：

• d[0] = a[0]
• d[i] = a[i] - a[i-1]

这相当于除第一项外，差分数组的每一项都是原数组前后两项的差值。

那么从差分数组到原数组的公式为：

• d[0] = a[0]
• a[i] = a[i-1] + d[i]

2. 性质

当我们希望对原数组的某一个区间 [l, r] 施加一个增量 x 时，差分数组 d 对应的变化是：d[l] 增加 x，d[r+1] 减少 x，并且这种操作是可以叠加的。

例如：a = [1, 2, 3, 4, 5, 6]，对 a[2] 到 a[4] 之间的所有数加上 $3$，变为 [1, 2, 6, 7, 8, 6]，那么差分数组也就从 [1, 1, 1, 1, 1, 1] 变成了 [1, 1, 4, 1, 1, -2]。

也就是说，当我们需要对原数组的不同区间施加不同的增量，我们只要按规则修改差分数组即可。

---

1. Leetcode 刷题笔记——差分数组，知乎，https://zhuanlan.zhihu.com/p/478120079 ↩︎