前缀和（prefix sum）也就是由一个数组的前 n 项和构成的新数组，而差分（difference）则是前缀和的逆运算，由一个数组邻项之差构成的新数组。

一维前缀和与差分

基本应用

一维前缀和用于快速求出静态数组在一个区间 [l, r] 上的区间和：\sum\limits_{k=l}^r a_k = s_r - s_{l - 1}。由于存储时数组的 0 位通常留空，且令 s_0 = 0，上述公式当 l = 1 时也成立。

一维差分通常用于快速处理区间加/减同一个数的信息。若令 d_n = a_n - a_{n - 1}，则对区间 [l, r] 的所有数同时 +k 时，差分数列的 d_l 将自增 k，而 d_{r + 1} 将自减 k。若是左闭右开或者连续的变量（例如对坐标 x_1, x_2 的线段染色），则是 d_{x_2} 自增 k。

优化

对于复杂的表达式，化简后可能也可以使用前缀和进行优化。

例如，若数组 x_i, y_i 已知，给定多组 x, y 和 m，计算表达式：

\sum_{i = 1}^m (x_i - x)^2 + (y_i - y)^2

则可以将表达式展开得到：

\sum_{i = 1}^m \left( x_i^2 + y_i^2 \right) - 2 x \sum_{i = 1}^m x_i - 2 y \sum_{i = 1}^m y_i + 2m \left( x^2 + y^2 \right).

这时候只需要维护 x_i^2 + y_i^2，x_i，y_i 三组前缀和即可。

二维前缀和与差分

定义

二维前缀和

对于给定的一个二维数组 a_{ij}，其二维前缀和定义为

s_{mn} = \sum_{i=1}^m \sum_{j=1}^n a_{ij} = \sum_{i\le m, j \le n} a_{ij}.

也可以逐维度定义，先对每一行（对列，即对第一维）定义前缀和：

s^{(1)}_{in} = \sum_{j = 1}^n a_{ij};

再对每一列求和，定义二维前缀和：

s_{mn} = \sum_{i=1}^m s_{in}^{(1)}.

二维差分

二维差分并不容易直观定义，可以借助逐维度差分定义。先定义每一行的前缀和：

d_{mn}^{(1)} = a_{mn} - a_{m,n-1};

然后再对每一列差分，定义二维前缀和：

d_{mn} = d_{mn}^{(1)} - d_{m-1,n}^{(1)};

两公式合起来就是：

d_{mn} = a_{mn} - a_{m,n-1} - a_{m-1, n} + a_{m-1,n-1}.

当由二维差分还原原数列时，由上式变形得到：

a_{mn} = a_{m,n-1} + a_{m-1,n} - a_{m-1,n-1} + d_{mn}.

应用

矩形区域和

使用二维前缀和求矩形区域 [a, c] \times [b, d] 的和时，公式如下：

\sum_{i=a}^{c} \sum_{j=b}^{d} = s_{cd} - s_{a-1,d} - s_{c,b-1} + s_{a-1,b-1}.

这一公式可以借助矩形面积理解：我们需要求出下图中蓝色的面积，而 s_{cd} 是 [0, c] \times [0, d] 的面积，就需要减去图中红色和蓝色矩形的面积，但减去 s_{a-1, d} 和 s_{c, b - 1} 又重复减去了 [0, a - 1] \times [0, b - 1] 的面积两次，因此又需要加回 s_{a-1, b-1}。

二维区域加

Overplanting S

使用二维差分，当给矩形区域 [l_1, r_1] \times [l_2, r_2] 中的整数格点都加上 k 时，对应的二维差分数组的变化为：

d_{l_1,l_2} + k, d_{l_1, r_2 + 1} - k, d_{r_1 + 1, l_2} - k, d_{r_1 + 1, r_2 + 1} + k

若是连续的矩形区域 [x_1, x_2] \times [y_1, y_2]，则是

d_{x_1,y_1} + k, d_{x_1, y_2} - k, d_{x_2, y_1} - k, d_{x_2, y_2} + k

其他前缀运算

异或前缀和

由于异或具有特殊的对合性（即，对任意二进制数 x，有 x \oplus x = 0），异或也可以用前缀和来简化运算。异或的对合性也可以认为是异或加减法的一致性，也即通常的加法、减法，对于异或运算是同一个操作。

对于一个二进制数构成的数组 (a_i)_{i = 0}^n，定义其异或前缀和 s：

s_1 = a_1, s_n = s_{n - 1} \oplus a_n.

则区间 [l, r] 的异或和

\bigoplus_{i = l}^r a_i = s_r \oplus s_{l - 1}.

同时，0 是异或的单位元，利用单位元也可以解决许多异或的问题。

前缀最值

由于不可差分性，前缀最大值只能实现查询 [1, i] 区间的最大值。如果需要查询任意区间，需要使用 ST 表。