定义

对于一个数组a[n]a[n]，如果对它有着频繁的区间操作（例如第5个到第60个数增加2，或第6个到第40个数减去2）。这个时候，暴力的做法时，直接用循环去操作，但是这样做的时间复杂度很大。所以对于这样的问题，可以使用差分数组。

具体做法

差分其实就是数据之间的差，什么数据的差呢？就是上面所给的原始数组a[n]的相邻元素之间的差值，我们令d[i]=a[i+1]-a[i]，一遍for循环即可将差分数组求出来。例如下面这个数组。

据此，可以发现两条差分数组的性质：

  • a[i]等于d[i]的前缀和
  • a[i]的前缀和可以通过如下公式来求得：
    • sumx=∑i=1xax=∑i=1x∑j=1idi=∑i=1x(x−i+1)×disum_x=\sum_{i=1}^{x}a_x=\sum_{i=1}^{x}\sum_{j=1}^{i}d_i=\sum_{i=1}^{x}(x-i+1)\times d_i

用途

差分数组主要支持两种操作：1、区间修改；2、单点查询
根据性质一，可以得到若对某个区间[L, R] 增加一个数 x，只需要使 d[L] += x; d[R + 1] -= x; 即可实现对区间的批量修改，而查询时只需要求前缀和查询单个元素，或者通过上述性质二的公式查询前缀和/区间和即可

区间修改

对上面那个表的数组作下面两个操作：

  • 将区间 [1,4] 的数值全部加上3
  • 将区间 [3,5] 的数值全部减去5
    其实当你将原始数组中元素同时加上或者减掉某个数，那么他们的差分数组其实是不会变化的。

    只有 d[1]和d[5]发生了变化，而d[2],d[3],d[4]却保持着原样。

当对一个区间进行增减某个值的时候，它的差分数组对应的区间左端点的值会同步变化，而它的右端点的后一个值则会相反地变化，其实这个很好理解

更新原数组

因为我们的差分数组是由原始数组的相邻两项作差求出来的，即 d[i]=a[i]-a[i-1]；那么我们能不能反过来，求得一下修改过后的a[i]呢？

直接反过来即得 a[i]=a[i-1]+d[i]

1
2
for(int i=1;i<=n;i++)
    a[i]=a[i-1]+d[i];

参考资料

[1] https://blog.csdn.net/qq_31601743/article/details/105352885
[2] https://blog.csdn.net/qq_44786250/article/details/100056975
[3] https://www.jianshu.com/p/2a4e861b44ae
[4] https://www.cnblogs.com/COLIN-LIGHTNING/p/8436624.html