差分算法

差分其实就是数据之间的差，就是所给的原始数组的相邻元素之间的差值，我们令d[i]=a[i+1]-a[i]，一遍for循环即可将差分数组求出来。

其实差分数组是一个辅助数组，从侧面来表示给定某一数组的变化，一般用来对数组进行区间修改的操作

当对一个区间进行增减某个值的时候，他的差分数组对应的区间左端点的值会同步变化，而他的右端点的后一个值则会相反地变化。

1. [L, R] + v ==> d[L] + v, d[R + 1] -v
2. 把标记后的差分数组，进行一次前缀和。

1. d[L] + v <==> [L, n-1] + v

2. d[R+1] - v <==> [R+1, n-1] - v

3. d[L] + v ,d[R+1] - v <==>[L, R] + v, [R+1, n-1] - v

1. d初始可赋0

2. 然后按照上述公式赋值

3. 之后用前缀和，将差分数组从前往后依次求和

4. 再加上原来数组对应的数即可