差分数组 • Arshe's site

基础原理#

对于一个数组arr它有相对应的差分数组diff，有以下关系：

diff[0] = arr[0]
diff[i] = arr[i] - arr[i - 1]	i = 1, 2, 3...

cpp

如果有一个差分数组diff也可以通过下面的公式转换出唯一的原数组arr：

arr[0] = diff[0]
arr[i] = arr[i - 1] + diff[i]	i = 1, 2, 3...

cpp

或

arr[i] = \sum_{\substack{k = 0}}^{i} diff[k]

i = 0, 1, 2…

使用场景#

当需要对原数组arr进行大量区间性的更新时，使用差分数组可以极大的减少时间复杂度

假设我有一个数组queries

queries = [left, right, value]

cpp

此数组的含义为，我要在原数组起始索引为left，结束索引为right的区间内的值都进行value的更新，如：

原数组arr = [2, 0, 2, 5]
queries1 = [1, 3, 3] // 则代表着我要将arr中索引从1到3的数都加3,为
操作后arr = [2, 3, 5, 8]

queries2 = [0, 2, -1] // 则代表着我要将arr中索引为0到2的数都加上-1,为
操作后arr = [1, 2, 4, 8]

cpp

聪明的你读到这肯定觉得很简单嘛，我们只需要读取queries[0]和queries[1]获取区间，再读取queries[2]获取更新值便可以进行遍历更改。

但是你有没有想过如果更新区间不是1-3和0-2这样的小区间，而是跨度足有几百上千并且不止做一次更新，你又遍历去暴力求值吗？

引入差分数组#

如果我们将差分数组引入到上面的场景，我们更新就不需要遍历原数组，而是修改差分数组的两个值便可，先说结论：

queries = [left, right, value] // 要做的更新
diff[left] += value
diff[right + 1] -= value

cpp

更新时，像上式更改差分数组diff即可，再根据一个差分数组可以转换出唯一原数组原则，便可得到更新后的原数组

为什么可以这样做呢？

在arr中我们要修改索引left到索引right的值，根据差分数组的定义，因为是做差，所以差分数组从索引left + 1到索引right的值是不变的（相邻元素经历相同变化后差值不变），唯一变的就是索引为left和right + 1的值，因为这是变化的临界点。

arr[left]与arr[left - 1]的差值增加了value，所以有diff[left] += value,

arr[right + 1]与arr[right]的差值减少了value，所以有diff[right + 1] -= value。

真题实战#

多说无益，上题