算法花园

差分是一种和前缀和相对的策略，可以当做是 求和 的逆运算
求差分数据的公式 #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$

例题

• 798. 得分最高的最小轮调 - 力扣（LeetCode） (leetcode-cn.com)

和树状数组区别 #card

• 树状数组：单点更新，区间查询

• 差分数组：区间更新，单点查询