[AcWing]前缀和&差分
前缀和与差分主要学习其思想和应用场景,其本质与数学相关度更高,模板意义并不大。
一、前缀和
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 |
|
1.2 前缀和矩阵
1.2.1 算法原理
代码已经在 GITHUB 开源,👉点击直达👈。
同样的,我们结合 AcWing 的 796 题为例子。简单概括一下就是对 a 矩阵(二维数组)中 [(x1, y1), (x2, y2)] 范围的子矩阵元素进行求和运算。可以参考以下示意图,我们要求解的就是 $S_4$ 子矩阵内所有元素的和。
在这个示意图中,我们不难得出以下公式(注意大写 $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 |
|
二、差分
差分,也就是前缀和的逆过程。例如: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}
$$
补充:这里需要注意一个问题,在生成差分序列时建议按照以下方式进行操作:
- 假设 a 序列为一个全为 0 的序列,记为 a’,那么对应的差分序列 b 也就是全 0 的。
- 那么 a 序列的实际值就等效于 a’ 序列中对应位置加上固定值 c,而这个 c 就是 a 序列的实际值(例如:$a_1$ 可以看成 $a^{‘}_{1} + a_1$)。
- 依次处理 a 序列的每个值,就可以生成对应的差分序列。
由于该问题处理 a 序列的加值问题会在其差分序列 b 中先处理,所以利用这一点可以巧妙地将生成差分数组的操作转为该题目的一个子问题进行处理。
下面的差分矩阵生成也差不多,主要还是理解(其实这里我讲的不好,确实比较绕)。
2.1.2 算法代码示例
1 |
|
2.2 差分矩阵
2.2.1 算法原理
代码已经在 GITHUB 开源,👉点击直达👈。
同样的,我们结合 AcWing 的 798 题为例子。简单概括一下就是对 a 矩阵(二维数组)中 [(x1, y1), (x2, y2)] 范围的子矩阵的每个元素都加上固定值 c。可以参考以下示意图(与前面介绍 a 矩阵的前缀和矩阵时做的图有所不同,这里应该是基于 b 矩阵绘制的图),我们要求解的就是 a 矩阵经过操作后的样子。
在这个示意图中,我们不难得出以下推导公式:
$$
\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 |
|