前缀和#

前缀和用于查询区间和．

定义 $s[i]$ 表示区间 $[1,i]$ 之间所有元素的和（即前 $i$ 个数的和），不难发现，区间 $[l,r]$ 的和为 $s[r] - s[l-1]$．

计算 $s$ 数组可以使用递推的方式，有 $s[i] = s[i-1] + a[i]$．

差分#

差分用于区间修改，是前缀和的逆运算．

定义 $d[i]$ 表示 $a[i]$ 相对 $a[i-1]$ 变化了多少，即 $d[i] = a[i] - a[i-1]$．

当想要对 $[l, r]$ 增加 $x$ 时，只需要将 $d[l]$ 增加 $x$，$d[r+1]$ 减少 $x$．

如果想要将差分数组还原成原数组，可以使用下面的公式：$a[i] = a[i-1] + d[i]$．