dsa

差分

差分，是一种和前缀和相对的策略，可以当做是求和的逆运算。这种策略是，令 $b_i=\{\begin{array}{ll}{a}_i-a_{i-1}& i\in [2,n]\\ a_1& i=1\end{array}$

简单性质：

• $a_i$ 的值是 $b_i$ 的前缀和，即 $a_i=\sum _{i=1}^n{f}_i$
• 计算 $a_i$ 的前缀和 sum= $\sum _{i=1}^n{a}_i=\sum _{i=1}^n\sum _{j=1}^i{f}_j=\sum _i^n(n-i+1)f_i$

它可以维护多次对序列的一个区间加上一个数，并在最后询问某一位的数或是多次询问某一位的数（ 修改操作一定要在查询操作之前 )

譬如使[l,r]中的每个数加上一个k，就是

$b_l\leftarrow b_l+k,b_{r+1}\leftarrow b_{r+1}-k$

最后做一遍前缀和就可恢复原数组。

参考

• 前缀和 & 差分 - OI Wiki
• P3397 地毯 - 洛谷 : 这题是2维的，但也能用一维的差分解决