前缀和与差分主要学习其思想和应用场景，其本质与数学相关度更高，模板意义并不大。

一、前缀和

1.1 前缀和序列

1.1.1 算法原理

代码已经在 GITHUB 开源，👉点击直达👈。

要想研究前缀和序列就需要结合具体的应用场景，这里就以 AcWing 的 795 题为例子。简单概括一下就是对 a 序列（数组）中 [left, right] 范围的元素进行求和运算。

首先，我们必须知道什么是前缀和序列。我们假设 a 序列为：

$$
a_1,\ a_2,\ a_3,\ …,\ a_n \quad and \quad n \in 1, 2, 3, …
\tag{1}
$$

那么 a 序列的前缀和序列就是：

$$
\begin{cases}
s_0 = 0,\\
s_n = s_{n-1} + a_n \quad and \quad n \in 1, 2, 3, …
\end{cases}
\tag{2}
$$

所以，我们要对 a 序列 [left, right] 范围的元素进行求和运算，也就是计算：

$$
res = a_{left} + … + a_{right}
\tag{3}
$$

那么，我们可以很容易推导得到以下公式：

$$
\begin{aligned}
res = \quad & a_1 + a_2 + … + a_{left-1} + a_{left} + … + a_{right} - \\
& a_1 + a_2 + … + a_{left-1} \\
= \quad & s_{right} - s_{left-1}
\end{aligned}
\tag{4}
$$

1.1.2 算法代码示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * @brief 计算 a 数组中从第 left 个数到第 right 个数的和
 * @param a 待处理数组
 * @param s a 的前缀和数组
 * @param left 区间左边界
 * @param right 区间右边界
 * @return a 数组中从第 left 个数到第 right 个数的和
 */
static int prefixSum(vector<int>& a, vector<int>&s, int left, int right) {
    // 获取 a 数组长度
    const int n = static_cast<const int>(a.size());

    // 计算 a 的前缀和数组 s
    s[0] = 0;   // 定义起始数
    for (int i = 1; i <= n; i++) {
        s[i] = s[i - 1] + a[i];
    }

    // 通过公式快速计算
    int res = s[right] - s[left - 1];

    // 返回结果
    return res;
}

1.2 前缀和矩阵

1.2.1 算法原理

代码已经在 GITHUB 开源，👉点击直达👈。

同样的，我们结合 AcWing 的 796 题为例子。简单概括一下就是对 a 矩阵（二维数组）中 [(x1, y1), (x2, y2)] 范围的子矩阵元素进行求和运算。可以参考以下示意图，我们要求解的就是 $S_4$ 子矩阵内所有元素的和。

图 1.2.1 a 矩阵示意图

在这个示意图中，我们不难得出以下公式（注意大写 $S$ 为图中标记区域，小写 $s$ 表示对应的子矩阵的前缀和）（容易推出，但是难以理解。注意是基于 a 矩阵的描述即可，此刻还没有涉及到关于 s 矩阵的事情）：

$$
\begin{aligned}
S_4 = \quad & s_{x_2y_2} - S_1 - S_2 + S_3 \\
= \quad & s_{x_2y_2} - s_{x_2(y_1-1)} - s_{(x_1-1)y_2} + s_{(x_1-1)(y_1-1)} \\ \\
and & \quad 1 \leq x \leq m \quad 且 \quad 1 \leq y \leq n
\end{aligned}
\tag{5}
$$

同时为了避免计算出现不确定因素，我们规定：

$$
s_{00} = s_{01} = s_{10} = a_{00} = a_{01} = a_{10} = 0
\tag{6}
$$

讨论了计算的核心公式，下面来讨论一下怎么得到 s 矩阵。其实 s 矩阵（a 矩阵的前缀和矩阵）就是将 a 矩阵中一片区域“浓缩”到一个点。因为在 s 矩阵中，每个位置的存储的元素值就代表了在 a 矩阵中一片区域的所有元素的算术运算和。例如：在 s 矩阵中 $(x_3, y_3)$ 位置存储的值就是 a 矩阵中以 $(0, 0)$ 为左上顶点，以 $(x_3, y_3)$ 为右下顶点的区域中所有元素的算术运算和。

和核心计算公式比较类似的，我们可以轻松得出（可以参考上面的图，这里不另外新画图了）：

$$
s_{xy} = s_{(x-1)y} + s_{x(y-1)} - s_{(x-1)(y-1)} + a_{xy}
\tag{7}
$$

1.2.2 算法代码示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
using matrix = vector<vector<int>>; // 定义矩阵
/**
 * @brief 计算矩阵中 (x1, y1) 到 (x2, y2) 的子矩阵的元素和
 * @param a 待处理数组
 * @param s a 的前缀和数组
 * @param x1 子矩阵左上角行坐标
 * @param y1 子矩阵左上角列坐标
 * @param x2 子矩阵右下角行坐标
 * @param y2 子矩阵右下角列坐标
 * @return 矩阵中 (x1, y1) 到 (x2, y2) 的子矩阵的元素和
 */
static int prefixSum(matrix& a, matrix& s, int x1, int y1, int x2, int y2) {
    // 计算矩阵规模 m x n
    const int m = static_cast<const int>(a.size());
    const int n = static_cast<const int>(a[0].size());

    // 计算前缀和矩阵 s
    s[0][0] = s[0][1] = s[1][0] = 0;  // 定义起始数
    for (int x = 1; x <= m; x++) {
        for (int y = 1; y <= n; y++) {
            s[x][y] = s[x][y - 1] + s[x - 1][y] - s[x - 1][y - 1] + a[x][y];
        }
    }

    // 根据公式快速计算
    int res = s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1];

    // 返回结果
    return res;
}

二、差分

差分，也就是前缀和的逆过程。例如：s 是 a 的前回合，那么 a 就是 s 的差分。但是为了降低理解难度，避免混淆，下面我们统一使用 b 代表 a 的差分。

2.1 差分序列

2.1.1 算法原理

代码已经在 GITHUB 开源，👉点击直达👈。

与前缀和序列不同的是，这是类似于“已知前缀和，求源”的过程，也就是前回合的逆过程。同样的，还是以 AcWing 的 797 题为例子。简单概括一下就是对 a 序列（数组）中以 [left, right] 为范围的子序列的每个元素都加上一个固定值 c。

a 序列在前面已经介绍过了（详见 $公式(1)$），这里不赘述。我们直接来看什么是差分序列：

$$
\begin{cases}
b_0 = 0, \\
b_n = a_n - a_{n-1} \quad and \quad n \in 1, 2, 3, …
\end{cases}
\tag{8}
$$

那么对 a 序列中以 [left, right] 为范围的子序列的每个元素都加上一个固定值 c 就是：

$$
\begin{aligned}
\because & \quad b_1 + c \quad \land \quad a_1 = b_0 + b_1 \quad \land \quad b_0 = 0 \\
\therefore & \quad a_1 + c \quad = \quad b_1 + c \\
\therefore & \quad a_2 + c \quad = \quad b_1 + b_2 + c \\
& \qquad … \\
\therefore & \quad a_n + c \quad = \quad b_1 + b_2 + … + b_n + c
\end{aligned}
\tag{9}
$$

也就是 $b_1 + c$ 那么就会导致 $a_1$ 之后的所有 a 序列中的元素 $+ c$，因为大家都包含 $b_1$。所以，我们可以轻松地推出：

$$
\begin{aligned}
& (a_{left} + c) + (a_{(left+1)} + c) + … + (a_{right} + c) \\
& = \quad b_{left} + c \quad \land \quad b_{(right + 1)} - c
\end{aligned}
\tag{10}
$$

补充：这里需要注意一个问题，在生成差分序列时建议按照以下方式进行操作：

  1. 假设 a 序列为一个全为 0 的序列，记为 a’，那么对应的差分序列 b 也就是全 0 的。
  2. 那么 a 序列的实际值就等效于 a’ 序列中对应位置加上固定值 c，而这个 c 就是 a 序列的实际值（例如：$a_1$ 可以看成 $a^{‘}_{1} + a_1$）。
  3. 依次处理 a 序列的每个值，就可以生成对应的差分序列。

由于该问题处理 a 序列的加值问题会在其差分序列 b 中先处理，所以利用这一点可以巧妙地将生成差分数组的操作转为该题目的一个子问题进行处理。

下面的差分矩阵生成也差不多，主要还是理解（其实这里我讲的不好，确实比较绕）。

2.1.2 算法代码示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
/**
 * @brief 利用公式“将 a 数组中 [left, right] 之间的每个数加上 c”，计算在差分数组 b 中进行，结果需要回馈更新给 a
 * @param b a 的差分数组
 * @param left 区间左边界
 * @param right 区间右边界
 * @param c 待加的定值
 */
static void difference_insert(vector<int>& b, int left, int right, int c) {
    // 根据公式快速计算
    b[left] += c;
    b[right + 1] -= c;
}

/**
 * @brief 将 a 数组中 [left, right] 之间的每个数加上 c
 * @param a 待处理数组
 * @param b a 的差分数组
 * @param left 区间左边界
 * @param right 区间右边界
 * @param c 待加的定值
 */
static void difference(vector<int>& a, vector<int>& b, int left, int right, int c) {
    // 计算 a 数组长度
    const int n = static_cast<const int>(a.size());

    // 生成差分数组 b
    a[0] = b[0] = 0;    // 初始化起始数
    for (int i = 1; i <= n; i++) {
        // 假设 a 数组的初始值全是 0
        // 那么实际的 a 数组可以看成假设的 a 数组在 [i, i] 之间的每个数加上 a[i]
        difference_insert(b, i, i, a[i]);   // 利用公式生成差分数组（注意，该步与实际公式没有关系）
    }
    // 暴力计算版：生成差分数组 b
    // 建议理解上述方法，不然在矩阵中不便于使用暴力计算版方法生成对应的差分矩阵
    //for (int i = 1; i <= n; i++) {
    //    b[i] = a[i] - a[i - 1];
    //}

    // 根据公式快速计算
    // 注意：执行 n 次以下是不划算的
    difference_insert(b, left, right, c);

    // 将计算结果回归到 a 数组中
    // 从这一步可以看出，
    // 如果操作“将 a 数组中 [left, right] 之间的每个数加上 c”只执行 < n 次是不划算的，
    // 因为这个算法最后始终要进行 n 次遍历，
    // 所以只有在大量进行上述操作时，该算法才具有高效性。
    for (int i = 1; i <= n; i++) {
        b[i] += b[i - 1];   // 先将 b 数组转为自己的前缀和数组
        a[i] = b[i];        // 将结果复制到 a 数组，即可更新 a 数组
    }
}

2.2 差分矩阵

2.2.1 算法原理

代码已经在 GITHUB 开源，👉点击直达👈。

同样的，我们结合 AcWing 的 798 题为例子。简单概括一下就是对 a 矩阵（二维数组）中 [(x1, y1), (x2, y2)] 范围的子矩阵的每个元素都加上固定值 c。可以参考以下示意图（与前面介绍 a 矩阵的前缀和矩阵时做的图有所不同，这里应该是基于 b 矩阵绘制的图），我们要求解的就是 a 矩阵经过操作后的样子。

图 2.2.1 b 矩阵示例图

在这个示意图中，我们不难得出以下推导公式：

$$
\begin{aligned}
\because & \quad b_{11} + c \quad \land \quad a_{11} = b_{00} + b_{01} + b_{10} + b_{11} \quad \land \quad b_{00} = b_{01} = b_{10} = 0 \\
\therefore & \quad a_{11} + c \quad = \quad b_{11} + c \\
& \quad … \\
\therefore & \quad a_{xy} + c \quad = \quad b_{11} + … + b{xy} + c
\end{aligned}
\tag{11}
$$

类似于差分序列，就是 $b_{xy} + c$ 那么就会导致 a 矩阵中以 $(x, y)$ 为左上角，以 $(m, n)$ 的区域的所有元素都会 $+ c$，因为大家都包含 $b_{xy}$。所以，我们可以轻松地推出：

$$
\begin{aligned}
& (a_{x1y1} + c) + (a_{x1(y1+1)} + c) + … + (a_{x2(y2-1)} + c) + (a_{x2y2} + c) \\
& = \quad b_{x1y1} + c \quad \land \quad b_{x1(y2 + 1)} - c \quad \land \quad b_{(x2+1)y1} - c \quad \land \quad b_{(x2+1)(y2+1)} + c
\end{aligned}
\tag{10}
$$

2.2.2 算法代码示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
using matrix = vector<vector<int>>; // 定义矩阵
/**
 * @brief 利用公式"将矩阵中 (x1, y1) 到 (x2, y2) 的子矩阵的每个元素都加上固定值 c"，计算在差分矩阵 b 中进行，结果需要回馈更新给 a
 * @param b a 矩阵的差分矩阵
 * @param x1 子矩阵左上角行坐标
 * @param y1 子矩阵左上角列坐标
 * @param x2 子矩阵右下角行坐标
 * @param y2 子矩阵右下角列坐标
 * @param c 固定值
 */
static void difference_insert(matrix& b, int x1, int y1, int x2, int y2, int c) {
    // 根据公式快速计算
    b[x1][y1] += c;
    b[x1][y2 + 1] -= c;
    b[x2 + 1][y1] -= c;
    b[x2 + 1][y2 + 1] += c;
}

/**
 * @brief 将矩阵中 (x1, y1) 到 (x2, y2) 的子矩阵的每个元素都加上固定值 c
 * @param a 待处理矩阵
 * @param b a 矩阵的差分矩阵
 * @param x1 子矩阵左上角行坐标
 * @param y1 子矩阵左上角列坐标
 * @param x2 子矩阵右下角行坐标
 * @param y2 子矩阵右下角列坐标
 * @param c 固定值
 */
static void difference(matrix& a, matrix& b, int x1, int y1, int x2, int y2, int c) {
    // 计算矩阵规模
    const int m = static_cast<const int>(a.size());
    const int n = static_cast<const int>(a[0].size());

    // 计算差分矩阵 b
    b[0][0] = b[0][1] = b[1][0] = a[0][0] = a[0][1] = a[1][0] = 0; // 初始化起始数
    for (int x = 1; x <= m; x++) {
        for (int y = 1; y <= n; y++) {
            difference_insert(b, x, y, x, y, a[x][y]);
        }
    }

    // 根据公式快速计算
    // 注意：执行 m x n 次以下是不划算的
    // 原因自己分析或参考 Acwing797.差分.cpp
    difference_insert(b, x1, y1, x2, y2, c);

    // 将计算结果回归到 a 数组中
    for (int x = 1; x <= m; x++) {
        for (int y = 1; y <= n; y++) {
            b[x][y] += b[x - 1][y] + b[x][y - 1] - b[x - 1][y - 1]; // 先将 b 矩阵转为自己的前缀和矩阵
            a[x][y] = b[x][y];  // 将结果复制到 a 矩阵，即可更新 a 矩阵
        }
    }
}