【算法基础】差分

Fivk

2021 年 11 月 21 日

1149 次浏览

暂无评论

1643字数

算法基础

类似于数学中的求导和积分，**差分可以看成前缀和的逆运算**。

### 差分数组：

首先给定一个原数组`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`数组 。

**知道了差分数组有什么用呢？** 别着急，慢慢往下看。

话说有这么一个问题：

给定区间`[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 日