差分数组

差分数组其实就是用来描述另一个数组（暂且称作原始数组）的元素变化情况的数组。

差分数组的第一个元素（d[0]）与原数组相同（a[0]），往后，d[i] = a[i] - a[i - 1]。

以原数组 arr = [0, 2, 5, 4, 9, 7, 10, 0] 为例，其差分数组为 d = [0, 2, 3, -1, 5, -2, 3, -10]。

图片来自：https://cloud.tencent.com/developer/article/1629357

这个差分数组有什么用呢？我们所知道的是，这个差分数组是对原数组的一种描述，我们是可以通过遍历差分数组将原数组构造出来的。那么这种描述，是不是在某种场景下可以提供某种优势呢？

是的，这个场景就是频繁的大批量区间修改。

比如说，我想把下标 [1, 4] 范围内的元素都 +3。按传统手段，我们需要访问这四个元素，逐一修改。四个修改起来是很快的，但如果区间范围很大呢？又或者这种区间修改的操作经常出现呢？

如果我们把这个操作转换到差分数组起来，我们就会发现，同样是将 [1, 4] 范围内的元素都 +3，我们只需要 d[1] + 3，d[5] - 3 就可以了。因为差分数组描述的是原数组的相邻变化，而我们对原数组的一个区间内进行了同加或同减操作的话，其实只有区间边界产生了相对变化。因此无论我们对多大的区间进行同加/同减，在差分数组中只需要修改两个值。