原数组：$[3,1,4,1,5,9]$ 前缀和：$[3,4,8,9,14,23]$ 差分：$[3,-2,3,-3,4,4]$

一维前缀和

构建 $S_i = S_{i - 1} + a_i$

快速求$[l,r]$ 的和 $S_r -S_{l-1}$

二维前缀和

类比一维的情形，$S{i,j}$ 应该可以基于 $S{i-1,j}$ 或 $S_{i,j-1}$ 计算，从而避免重复计算前面若干项的和。但是，如果直接将 $S_{i-1,j}$ 和 $S_{i,j-1}$ 相加，再加上 $A_{i,j}$，会导致重复计算 $S_{i-1,j-1}$ 这一重叠部分的前缀和，所以还需要再将这部分减掉。

在已经预处理出二维前缀和后，要查询左上角为 $(i_1,j_1)$、右下角为 $(i_2,j_2)$ 的子矩阵的和，可以计算

这可以在 $O(1)$ 时间内完成

在二维的情形，以上算法的时间复杂度可以简单认为是 $O(mn)$，即与给定数组的大小成线性关系。但是，当维度 $k$ 增大时，由于容斥原理涉及的项数以指数级的速度增长，时间复杂度会成为 $O(2^kN)$，其中 $k$ 是数组维度，而 $N$ 是给定数组大小。因此，该算法不再适用。

一维差分

对于序列 $\{a_i\}$，它的差分序列 $\{D_i\}$ 是指

构造与修改可以统一

insert(i,i,a[i]);

insert(l,r,c);

给区间 $[l,r]$ 中每个数 $+c$： $$ \begin{align} b[l]\ &+!=c\ b[r+1]\ &-!=c \end{align} $$

在所有修改操作结束后，可以通过前缀和操作恢复更新后的 $\{a_i\}$ 的值。单次修改是 $O(1)$ 的。查询时，需要做一次 $O(n)$ 的前缀和操作，随后每次查询都是 $O(1)$ 的。

二维差分

void insert(int x1,int y1,int x2,int y2){
    b[x1][y1] += 1;
    b[x2 + 1][y1] -=1;
    b[x1][y2 + 1] -=1;
    b[x2 + 1][y2 + 1] +=1;
}

b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];