差分数组
差分是一种和前缀和相对的策略，可以当做是 {{c1 求和}} 的逆运算
求差分数据的公式 #card
- $b_{i}= \begin{cases}a_{i}-a_{i-1} & i \in[2, n] \ a_{1} & i=1\end{cases}$
性质
- ai 是 bi 的前缀和
- 计算前缀和 #card
- $\text { sum }=\sum_{i=1}^{n} a_{i}=\sum_{i=1}^{n} \sum_{j=1}^{i} b_{j}=\sum_{i}^{n}(n-i+1) b_{i}$
- 区间序列 [l,r] 加上一个数 k #card
- $b_{l} \leftarrow b_{l}+k, b_{r+1} \leftarrow b_{r+1}-k$
例题
和树状数组区别 #card
- 树状数组：单点更新，区间查询
- 差分数组：区间更新，单点查询