差分数组
差分数组
你有没有遇到过这种情况:需要给一个区间的数组都加或减一个数
以前我是蒟蒻所以只会用for循环
而现在有了差分数组再也不用因为这个问题被困扰了
引
对于一个数组的求和我们可以用前缀和的方法来求和
即:b[i] = a[i] + a[i-1]这样b[N]就是a数组的和
正文
与b[i] = a[i] + a[i-1]这样类似我们定义b为b[i] = a[i] - a[i-1]
| 数组 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| a | 0 | 4 | 7 | 3 | 6 | 9 | 1 | 5 |
| b | 0 | 4 | 3 | -4 | 3 | 3 | -8 | 4 |
现在如果我们想在[2,4]上加上3则
| 数组 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| a | 0 | 4 | 10 | 6 | 9 | 9 | 1 | 5 |
| b | 0 | 4 | 6 | -4 | 3 | 0 | -8 | 4 |
我们可以发现b数组上仅有b[2]和b[5]上有变化分别为+3 -3 |
||||||||
所以我们只需要在b[i] += d,b[j+1] -= d就可以实现[i,j]上都加上d |
||||||||
这样原本复杂度为O(N)变为了O(1) |
推荐博客
https://blog.csdn.net/qq_44786250/article/details/100056975