差分算法
差分算法可以用来维护区间的加减
我们假定有一个数组 \(a={1,2,3,4}\)
\(b\) 为数组 \(a\) 的差分数组。
\[b_i=\begin{cases} a_i - a_{i-1}&i \in [2,n]\\ a_1 & i=1 \end{cases} \]根据给定的数组 \(a={1,2,3,4}\) 我们很容易得知数组 \(b={1,1,1,1}\)
我们求数组 \(b\) 的前缀和数组，我们发现：
\[sum_b={1,2,3,4} \]\[a={1,2,3,4} \]数组 \(b\) 的前缀和数组和原数组 \(a\) 一样，我们再举个例子：
\[a={1,2,2,4} \]\[b={1,1,0,2} \]\[sum_b={1,2,2,4} \]我们搞清楚这个性质之后我们再回到原问题，维护区间和加减。
假定，我们要让区间 \([L,R]\) 的值整体加 \(k\) , 我们让 \(b[L] + k\) ， 再让 \(b[R+1] - k\) 再求前缀和就可以得到增加后的原数组 \(a\) 了。
用刚才的例子：
\[a={1,2,2,4} \]\[b={1,1,0,2} \]我们让区间 \([2,3]\) 加 \(1\) (下表从 \(1\) 开始）
\(b[L]+1\) 得： \(b={1,2,0,2}\)
如果在这个时候求前缀和：
\(a={1,3,3,5}\)
我们发现区间 \([2,4]\) 都加上了 \(1\) ，不符合预期。
所以，我们还要进行下一步操作：
\(b[R+1]-1\) 得： \(b={1,2,0,1}\)
再求前缀和：
\(a={1,3,3,4}\)
我们发现区间 \([2,3]\) 加上了 \(1\) ，符合预期。
这样一来，我们就知道了如何用差分维护区间和加减。
标签：前缀,差分,算法,数组,区间,我们 From： https://www.cnblogs.com/SCAtlas-lxy23/p/17999869一般来说，如果有 \(q\) 个操作，那么我们可以现在差分数组 \(b\) 上操作 \(q\) 次，再统一求前缀和，这样就可以做到 \(O(n)\) 修改了。