前缀和、差分

一维前缀和

包含 n 个元素的数组 $arr$
询问 q 次 $[L,R]$（下标从 L 到 R）的区间和 $sum[L,R]$
时间复杂度为 $O(nq)$

例如：
给出数组 arr : 1 3 7 5 2
询问区间和：
[2, 4] = 7 + 5 + 2 = 14
[0, 3] = 1 + 3 + 7 + 5 = 16
[3, 4] = 5 + 2 = 7

下面给出前缀和计算公式：
$$sum[i]=\{\begin{array}{ll}sum[i-1]+arr[i],& i>0\\ arr[0],& i=0\end{array}$$

那么，计算区间和 $sum[L,R]$ 即可用下面公式计算得到。
$$sum[L,R]=\{\begin{array}{ll}sum[R]-sum[L-1],& L>0\\ sum[R],& L=0\end{array}$$

数组   arr : 1 3 7 5 2
前缀和  sum : 1 4 11 16 18

$sum[2,4]=sum[4]-sum[1]=18-4=14$
$sum[0,3]=sum[3]=16=16$
$sum[3,4]=sum[4]-sum[2]=18-11=7$

一维差分

包含 n 个元素的数组 $arr$
给出差分数组：
$$d[i]=\{\begin{array}{ll}arr[i]-arr[i-1],& i>0\\ arr[i],& i=0\end{array}$$

数组 $arr$：1 3 7 5 2
差分 $d$：1 2 4 -2 -3

计算差分的前缀和 $su{m}_d$：1 3 7 5 2，可以发现差分的前缀和 $su{m}_d$ 与 $arr$ 相同。

现在若需要做 m 个操作 $arr[L,R]+v$（$arr$下标从 $L$ 到 $R$ 之间的值加个常数 $v$），那么时间复杂度为 $O(nm)$

现给出 3 个操作：$arr[2,4]+5$，$arr[1,3]+2$，$arr[0,2]-3$，即

arr[0] - 3; 
arr[1] + 2 - 3; 
arr[2] + 5 + 2 - 3; 
arr[3] + 5 + 2; 
arr[4] + 5;
1
2
3
4
5

那么数组 $arr$ 变为 -2, 2, 11, 12, 7

利用差分，给出结论：
$$arr[L,R]+v⟺d[L]+v,d[R+1]-v$$
$$arr[L,R]+v⟺\{\begin{array}{ll}d[L]+v,d[R+1]-v,& i>0\\ d[L]+v,& R=n-1\end{array}$$

如例子中：
$arr[2,4]+5⟺d[2]+5$
$arr[1,3]+2⟺d[1]+2,d[4]-2$
$arr[0,2]-3⟺d[0]-3,d[3]+3$
得到 $d$：-2 4 9 1 -5
计算新的差分 $d$ 的前缀和 $su{m}_d$：-2 2 11 12 7，正好是经过 $arr[2,4]+5$，$arr[1,3]+2$，$arr[0,2]-3$ 之后的 $arr$。