差分
定义
差分十一种和前缀和相对的策略，可以当作是求和的逆运算。
这种策略的定义是令
(
egin{cases}
a_i-a_{i-1}~~~~~~iin[2,n]\
a_1~~~~~~~~~~~~~~~~~i=1
end{cases}
)
简单性质:
- (a_i)的值是(b_i)的前缀和，即(a_n=sum^n_{i=1}b_i)
- 计算(a_i)的前缀和(sum=sum^n_{i=1}a_i=sum^n_{i=1}sum^i_{j=1}b_j=sum^n_i(n-i+1)b_i)
它可以维护多次对序列的一个区间加上一个数，并在最后询问某一位的数。注意修改操作一定要在查询操作之前。
示例
譬如使[l,r]中的每一个数加上一个k，就是
[b_1leftarrow b_l+k,b_{r+1}leftarrow b_{r+1}-k
]
其中(b_l+k=a_l+k-a{l-1},b{r+1}-k=a{r+1}-(a_r+k))
最后做一边前缀和就好了。