Loading... 类似于数学中的求导和积分,**差分可以看成前缀和的逆运算**。 ### 差分数组: 首先给定一个原数组`a`:`a[1], a[2], a[3],,,,,, a[n];` 然后我们构造一个数组`b` :` b[1] ,b[2] , b[3],,,,,, b[i];` 使得 `a[i] = b[1] + b[2 ]+ b[3] +,,,,,, + b[i]` 也就是说,`a`数组是`b`数组的前缀和数组,反过来我们把`b`数组叫做`a`数组的**差分数组**。换句话说,每一个`a[i]`都是`b`数组中从头开始的一段区间和。 考虑如何构造差分`b`数组? 最为直接的方法 如下: `a[0 ]= 0;` `b[1] = a[1] - a[0];` `b[2] = a[2] - a[1];` `b[3] =a [3] - a[2];` ........ `b[n] = a[n] - a[n-1];` 我们只要有`b`数组,通过前缀和运算,就可以在`O(n)` 的时间内得到`a`数组 。 **知道了差分数组有什么用呢?** 别着急,慢慢往下看。 <div class="tip inlineBlock success"> 话说有这么一个问题: 给定区间`[l , r]`,让我们把`a`数组中的`[ l, r]`区间中的每一个数都加上`c`,即 `a[l] + c , a[l+1] + c , a[l+2] + c ,,,,,, a[r] + c;` </div> 暴力做法是`for`循环`l`到`r`区间,时间复杂度`O(n)`,如果我们需要对原数组执行`m`次这样的操作,时间复杂度就会变成`O(n*m)`。有没有更高效的做法吗? **考虑差分做法。** 始终要记得,`a`数组是`b`数组的前缀和数组,比如对`b`数组的`b[i]`的修改,会影响到`a`数组中从`a[i]`及往后的每一个数。 首先让差分`b`数组中的 `b[l] + c` ,`a`数组变成 `a[l] + c ,a[l+1] + c,,,,,, a[n] + c;` 然后我们打个补丁,`b[r+1] - c`, `a`数组变成 `a[r+1] - c,a[r+2] - c,,,,,,,a[n] - c;` **为啥还要打个补丁?** **我们画个图理解一下这个公式的由来:** ![](https://blog.fivk.cn/usr/uploads/2021/11/237537124.png) `b[l] + c`,效果使得`a`数组中 `a[l]`及以后的数都加上了`c`(红色部分),但我们只要求`l`到`r`区间加上`c`, 因此还需要执行 `b[r+1] - c`,让`a`数组中`a[r+1]`及往后的区间再减去`c`(绿色部分),这样对于`a[r]` 以后区间的数相当于没有发生改变。 因此我们得出一维差分结论:给`a`数组中的`[ l, r]`区间中的每一个数都加上`c`,只需对差分数组`b`做 `b[l] + = c, b[r+1] - = c`。时间复杂度为`O(1)`, 大大提高了效率。 ### 总结: ![](https://blog.fivk.cn/usr/uploads/2021/11/1617496530.png) ### AC代码 ```cpp //差分 时间复杂度 o(m) #include<iostream> using namespace std; const int N = 1e5 + 10; int a[N], b[N]; int main() { int n, m; scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); b[i] = a[i] - a[i - 1]; //构建差分数组 } int l, r, c; scanf("%d%d%d", &l, &r, &c); b[l] += c; //将序列中[l, r]之间的每个数都加上c b[r + 1] -= c; for (int i = 1; i <= n; i++) { a[i] = b[i] + a[i - 1]; //前缀和运算 printf("%d ", a[i]); } return 0; } ``` 最后修改:2021 年 11 月 21 日 © 允许规范转载 打赏 赞赏作者 支付宝微信 赞 如果觉得我的文章对你有用,请随意赞赏