前缀和与差分是 OI 中十分重要且常见的基本算法。
前缀和
前缀和是一个数组的基础信息。
一维前缀和的定义为：
\[s_n=\displaystyle \sum_{1\leq i \leq n - 1} a_{i}
\]
可以通过递推求出：s[i] = s[i - 1] + a[i];
求出前缀和数组后，可以在 \(O(1)\) 时间内询问 \(a_l-a_r\) 之和。sum = s[r] - s[l - 1];
不难类推出二维前缀和：
$ s_{n,m} = \displaystyle \sum_{1\leq i \leq n - 1} \sum_{1\leq j \leq m - 1} a_{i,j}$
求出前缀和数组后，可以在 \(O(1)\) 时间内询问 \(a_{l1,r1}-a_{l2,r2}\) 之和。此处运用了容斥的思想。
sum = s[l2][r2] - s[l2][r1 - 1] - s[l1 - 1][r2] + s[l1 - 1][r1 - 1];
差分
通俗来说，差分是前缀和的逆运算。
定义一维差分数组为：
\[d_1 = a_1, d_i = a_i - a_{i - 1}
\]
这样，可以在 \(O(1)\) 时间内修改区间，而在 \(O(n)\) 时间内查询单点：
使 \(l-r\) 区间每一个数加上 \(1\)：
d[r + 1]--, d[l]++;
对差分数组使用前缀和查询。