二维差分和二维前缀和

更新

图床烂了，没备份，只能阴间再见了 2024-06-24

二维前缀和

我们先对用到的一些概念进行符号定义。

符号约定

我们用：

$$\mathbf{A} = (a_{ij}) = \left[ \begin{array}{cccc} a_{1,1} & a_{1,2} & \cdots & a_{1, n} \\ a_{2,1} & a_{2,2} & \cdots & a_{2, n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m, 1} & a_{m, 2} & \cdots & a_{m, n} \end{array} \right]_{m \times n}$$

表示一个 $m$ 行 $n$ 列的矩阵。其中，对于 $\forall i, j \in \mathbb{N}$ 且 $1 \leqslant i \leqslant m, 1 \leqslant j \leqslant n$ 有 $a_{i,j} \in \mathbb{Z}$.

我们用：

$$\mathbf{A}_{r_1 : r_2, \ c_1 : c_2} = \left[ \begin{array}{cccc} a_{r_1,\ c_1} & a_{r_1, \ c_1+1} & \cdots & a_{r_1, \ c_2} \\ a_{r_1+1, \ c_1} & a_{r_1+1, \ c_1+1} & \cdots & a_{r_1+1, \ c_2} \\ \vdots & \vdots & \ddots & \vdots \\ a_{r_2, \ c_1} & a_{r_2, \ c_1+1} & \cdots & a_{r_2, \ c_2} \end{array} \right]_{(r_2 - r_1 + 1) \times (c_2 - c_1 + 1)}$$

表示矩阵 $\mathbf{A}$ 的一个子块，其中 $r_1, r_2, c_1, c_2 \in \mathbb{N}$ 且 $1 \leqslant r_1 \leqslant r_2 \leqslant m$ 以及 $1 \leqslant c_1 \leqslant c_2 \leqslant n$.

我们定义集合：

$$M_{m \times n}(\mathbb{Z}) = \left\{ \mathbf{A} \ \middle| \ \forall i, j \in \mathbb{N} \land 1 \leqslant i \leqslant m \land 1 \leqslant j \leqslant n, \ a_{i,j} \in \mathbb{Z}\right\}$$

用函数：

$$\text{Sum} : M_{(r_2 - r_1 + 1) \times (c_2 - c_1 + 1)}(\mathbb{Z}) \rightarrow \mathbb{Z} \quad \text{Sum}(\mathbf{A}_{r_1 : r_2, \ c_1 : c_2}) = \sum_{i = r_1}^{r_2}\sum_{j = c_1}^{c_2} a_{i, j}$$

表示一个子块的元素之和。

定义函数：

$$\text{AddSubMat} : M_{m \times n}(\mathbb{Z}) \times \mathbb{N}^2 \times \mathbb{N}^2 \times \mathbb{Z}\rightarrow M_{m \times n}(\mathbb{Z}) \\ \text{AddSubMat}(\mathbf{A}, r_1, c_1, r_2, c_2, x) = \mathbf{C}$$

其中 $1 \leqslant r_1 \leqslant r_2 \leqslant m,1 \leqslant c_1 \leqslant c_2 \leqslant n$，$x \in \mathbb{Z}$ 且：

$$\mathbf{C} = (c_{ij})_{m \times n} = \begin{align*} \left\{ \begin{aligned} a_{ij} + x &, \quad \text{if} \ \ i \in [r_1, r_2] \land j \in [c_1, c_2] \\ a_{ij} &, \quad \text{else} \end{aligned} \right. \end{align*}$$

表示对矩阵一个子块里的所有元素加 $x$ 的操作。

定义函数：

$$\text{AddMatCell} : M_{m \times n}(\mathbb{Z}) \times \mathbb{N}^2 \times \mathbb{Z}\rightarrow M_{m \times n}(\mathbb{Z}) \\ \text{AddMatCell}(\mathbf{A}, r, c, x) = \mathbf{F}$$

其中 $1 \leqslant r \leqslant m, 1 \leqslant c \leqslant n$，$x \in \mathbb{Z}$ 且：

$$\mathbf{F} = (f_{ij})_{m \times n} \\ f_{ij} = \begin{align*} \left\{ \begin{aligned} a_{ij} + x &, \quad \text{if} \ \ i = r \land j = c \\ a_{ij} &, \quad \text{else} \end{aligned} \right. \end{align*}$$

表示对矩阵某个位置上的元素加 $x$ 的操作。

功能预告

二维前缀和在花费 $O(n^2)$ 的时间进行预处理之后， 能以 $O(1)$ 的复杂度回答 $\text{Sum}(\mathbf{A}_{r_1 : r_2, \ c_1 : c_2})$.

具体做法

我们首先定义前缀和函数：

$$\text{PreSum} : M_{m \times n} \times \mathbb{N} \times \mathbb{N} \rightarrow \mathbb{Z} \quad \text{PreSum}(\mathbf{A}, r, c) = \sum_{i = 1}^{r}\sum_{j = 1}^{c} a_{ij}$$

定义矩阵 $\mathbf{A}$ 的前缀和矩阵：

$$\begin{align*} \mathbf{S}_{\mathbf{A}} = (s_{ij}) &= (\text{PreSum}(\mathbf{A}, i, j)) \\ &= \left[ \begin{array}{cccc} \sum_{i = 1}^{1}\sum_{j = 1}^{1} a_{ij} & \sum_{i = 1}^{1}\sum_{j = 1}^{2} a_{ij} & \cdots & \sum_{i = 1}^{1}\sum_{j = 1}^{n} a_{ij} \\ \sum_{i = 1}^{2}\sum_{j = 1}^{1} a_{ij} & \sum_{i = 1}^{2}\sum_{j = 1}^{2} a_{ij} & \cdots & \sum_{i = 1}^{2}\sum_{j = 1}^{n} a_{ij} \\ \vdots & \vdots & \ddots & \vdots \\ \sum_{i = 1}^{m}\sum_{j = 1}^{1} a_{ij} & \sum_{i = 1}^{m}\sum_{j = 1}^{2} a_{ij} & \cdots & \sum_{i = 1}^{m}\sum_{j = 1}^{n} a_{ij} \\ \end{array} \right]_{m \times n} \end{align*}$$

形象地，前缀和矩阵 $\mathbf{S}_{ij}$ 等于原矩阵 $\mathbf{A}_{ij}$ 左上部分的所有元素之和。即如下图一所示的深橙色部分。

现在考虑如何根据原矩阵计算出前缀和矩阵。我们将 $\mathbf{S}_{rc}$ 划分：

$$\begin{align*} \mathbf{S}_{rc} &= \sum_{i = 1}^{r}\sum_{j = 1}^{c} a_{ij} \\ &= \underbrace{\sum_{i = 1}^{r - 1}\sum_{j = 1}^{c - 1} a_{ij}}_{\text{Part 1}} + \underbrace{\sum_{i = 1}^{r - 1} a_{ic}}_{\text{Part 2}} + \underbrace{\sum_{j = 1}^{c - 1} a_{rj}}_{\text{Part 3}} + a_{rc} \end{align*}$$

形象地，如下图二所示：

$\text{Part 1}$ 对应黄色部分，$\text{Part 2}$ 对应蓝色部分，$\text{Part 3}$ 对应绿色部分，$a_{rc}$ 对应橙色部分。

观察矩形面积，直观地有（马上仔细证）：

$$S_{OQYV} = S_{OQUR} + S_{OPWV} - S_{OPTR} + S_{TUYW} \tag{1}$$

注意到黄色部分加上蓝色部分即为 $\mathbf{S}_{r-1, c}$ 类似地，黄色部分加上绿色部分即为 $\mathbf{S}_{r, c-1}$. 于是考虑多添加一项 $\text{Part 1}$ 再减去 $\text{Part 1}$：

$$\begin{align*} \mathbf{S}_{rc} &= {\sum_{i = 1}^{r - 1}\sum_{j = 1}^{c - 1} a_{ij}} + \sum_{i = 1}^{r - 1} a_{ic} + \sum_{j = 1}^{c - 1} a_{rj} + a_{rc} \\ &= \left(\sum_{i = 1}^{r - 1}\sum_{j = 1}^{c - 1} a_{ij} + \sum_{i = 1}^{r - 1} a_{ic}\right) + \left(\sum_{i = 1}^{r - 1}\sum_{j = 1}^{c - 1} a_{ij} + \sum_{j = 1}^{c - 1} a_{rj}\right) - \sum_{i = 1}^{r - 1}\sum_{j = 1}^{c - 1} a_{ij} + a_{rc} \\ &= \sum_{i = 1}^{r - 1}\sum_{j = 1}^{c} a_{ij} + \sum_{i = 1}^{r}\sum_{j = 1}^{c - 1} a_{ij} - {\sum_{i = 1}^{r - 1}\sum_{j = 1}^{c - 1} a_{ij}} + a_{rc}\\ &= \mathbf{S}_{r-1, c} + \mathbf{S}_{r, c-1} - \mathbf{S}_{r-1, c-1} + a_{rc} \tag{2} \end{align*}$$

观察 $(2)$ 式，只需要求出 $\mathbf{S}_{r-1, c}$ 和 $\mathbf{S}_{r, c-1}$ 和 $\mathbf{S}_{r-1, c-1}$ 我们就可以立即得到 $\mathbf{S}_{r, c}$. 显然这些项的下标都在 $r$ 和 $c$ 之前，于是可以使用递推预处理：

for (int i = 1; i <= m; i++) {
    for (int j = 1; j <= n; j++) {
        s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j + 1] + a[i][j];
    }
}

预处理结束之后，我们考虑如何利用前缀和 $\mathbf{S}$ 回答查询 $\text{Sum}(\mathbf{A}_{r_1 : r_2, \ c_1 : c_2})$. 回想到我们刚刚递推预处理出 $\mathbf{S}$ 的递推公式：

$$\mathbf{S}_{rc} = \mathbf{S}_{r-1, c} + \mathbf{S}_{r, c-1} - \mathbf{S}_{r-1, c-1} + a_{rc}$$

显然我们可以对这一式子进行推广，把 $a_{rc}$ 替换为子块和 $\text{Sum}(\mathbf{A}_{r_1 : r_2, \ c_1 : c_2})$，即：

$$\mathbf{S}_{r_2, c_2} = \mathbf{S}_{r_1-1, c_2} + \mathbf{S}_{r_2, c_1-1} - \mathbf{S}_{r_1-1, c_1-1} + \text{Sum}(\mathbf{A}_{r_1 : r_2, \ c_1 : c_2}) \tag{3}$$

如下图，图三把图二的橙色部分替换成紫色区块，类似式 $(1)$ 的面积等式依然成立。严格的数学证明过程与 $(2)$ 式的推导类似，不再赘述。

对式 $(3)$ 进行移项，由于前缀和矩阵我们已经预处理计算完成，我们便能够在常数时间内回答询问 $\text{Sum}(\mathbf{A}_{r_1 : r_2, \ c_1 : c_2})$：

$$\text{Sum}(\mathbf{A}_{r_1 : r_2, \ c_1 : c_2}) = \mathbf{S}_{r_2, c_2} - \mathbf{S}_{r_1-1, c_2} - \mathbf{S}_{r_2, c_1-1} + \mathbf{S}_{r_1-1, c_1-1}$$

二维差分

功能预告

二维差分能在常数时间内维护 $\text{AddSubMat}$ 操作，在所有操作完成之后，以 $O(n^2)$ 的时间复原出原矩阵。

具体做法

我们定义矩阵 $\mathbf{A}$ 的差分矩阵为 $\mathbf{D}$ 当且仅当：

$$\mathbf{A} = \mathbf{S}_{\mathbf{D}}$$

即：

$$(a_{ij}) = (\text{PreSum}(\mathbf{D}, i, j))$$

即矩阵 $\mathbf{A}$ 是 $\mathbf{D}$ 的前缀和矩阵。

根据定义和式 $2$，我们可以立即得到：

$$\mathbf{A}_{r, c} = \mathbf{A}_{r-1, c} + \mathbf{A}_{r, c-1} - \mathbf{A}_{r-1, c-1} + \mathbf{D}_{r, c}$$

移项得到差分矩阵 $\mathbf{D}$ 的计算公式：

$$\mathbf{D}_{r, c} = \mathbf{A}_{r, c} - \mathbf{A}_{r-1, c} - \mathbf{A}_{r, c-1} + \mathbf{A}_{r-1, c-1} \tag{4}$$

到目前为止，我们只是对差分矩阵进行了定义和计算，但我们还不能看出它有什么具体的作用。接下来，我们将发掘它的良好性质，再看看怎样把好的性质用于高效维护 $\text{AddSubMat}$ 操作。

现在假设我们手中有一个矩阵 $\mathbf{A}$ 并根据式 $(4)$ 求出了它的差分矩阵 $\mathbf{D}$. 现在，对 $\mathbf{D}$ 的 $(r_0, c_0)$ 位置进行单点加 $x$ 的操作，即令 $\mathbf{D}' = \text{AddMatCell}(\mathbf{D}, r_0, c_0)$. 我们有：

$$\mathbf{D}'_{ij} = \begin{align*} \left\{ \begin{aligned} \mathbf{D}_{ij} + x &, \quad \text{if} \ \ i = r_0 \land j = c_0 \\ \mathbf{D}_{ij} &, \quad \text{else} \end{aligned} \right. \end{align*}$$

我们现在考察新的 $\mathbf{D}'$ 是哪一个矩阵 $\mathbf{A}'$ 的差分矩阵。根据定义，我们有 $\mathbf{A}' = \mathbf{S}_{\mathbf{D}'}$，现在分类计算 $\mathbf{A}'$ 的每一元素 $\mathbf{A}'_{rc}$ 的值：

1° 当 $r \in [r_0, m] \land c \in [c_0, n]$ 时：

$$\begin{align*} \mathbf{A}'_{rc} &= \text{PreSum}(\mathbf{D}', r, c) \\ &= \sum_{i = 1}^{r}\sum_{j = 1}^{c} \mathbf{D}'_{ij} \\ &= \left(\sum_{\substack{1 \leqslant i \leqslant r, 1 \leqslant j \leqslant c \\ i \neq r_0 \land j \neq c_0}} \mathbf{D}'_{ij}\right) + \mathbf{D}'_{r_0, c_0} \\ &= \left(\sum_{\substack{1 \leqslant i \leqslant r, 1 \leqslant j \leqslant c \\ i \neq r_0 \land j \neq c_0}} \mathbf{D}_{ij}\right) + \mathbf{D}_{r_0, c_0} + x \\ &= x + \sum_{i = 1}^{r}\sum_{j = 1}^{c} \mathbf{D}_{ij} \\ &= \text{PreSum}(\mathbf{D}, r, c) + x \\ &= \mathbf{A}_{rc} + x \end{align*}$$

即对于处在 $r_0$ 行 $c_0$ 列的右下部分所有位置来说，$\mathbf{A'}$ 的值比 $\mathbf{A}$ 增加了 $x$.

2° 当 $r \notin [r_0, m] \lor c \notin [c_0, n]$ 时：

$$\begin{align*} \mathbf{A}'_{rc} &= \text{PreSum}(\mathbf{D}', r, c) \\ &= \sum_{i = 1}^{r}\sum_{j = 1}^{c} \mathbf{D}'_{ij} \\ &= \sum_{i = 1}^{r}\sum_{j = 1}^{c} \mathbf{D}_{ij} \\ &= \text{PreSum}(\mathbf{D}, r, c) \\ &= \mathbf{A}_{rc} \end{align*}$$

即除了 1° 的情况以外，不处在 $r_0$ 行 $c_0$ 列的右下部分所有位置上 $\mathbf{A'}$ 的值和 $\mathbf{A}$ 相等。

综合两种情况，有：

$$\mathbf{A}'_{ij} = \begin{align*} \left\{ \begin{aligned} \mathbf{A}_{ij} + x &, \quad \text{if} \ \ r_0 \leqslant i \leqslant m \land c_0 \leqslant j \leqslant n \\ \mathbf{A}_{ij} &, \quad \text{else} \end{aligned} \right. \end{align*} \tag{5}$$

下面给出一个 $\mathbf{D}_{4 \times 5} = \mathbf{A}_{4 \times 5} = \mathbf{0}$，$r_0 = 1, c_0 = 4, x = 1$ 的直观例子：

我们可以发现，$\text{AddMatCell}(\mathbf{D}, r, c)$ 等价于 $\text{AddSubMat}(\mathbf{A}, r, c, m, n)$. 即对于差分矩阵的单点加操作等价于对原矩阵的右下块整片加操作。

那么反过来，$\text{AddSubMat}(\mathbf{A}, r, c, m, n)$ 也等价于 $\text{AddMatCell}(\mathbf{D}, r, c)$，所以，对原矩阵的右下块整片加操作可以被转化成在差分矩阵的单点加操作。试想，如果我们没有差分矩阵这一工具，要想对右下整片都加上 $x$，我们只能枚举右下块里的每一个位置，然后对每个位置单点加 $x$，但现在我们只需要在差分矩阵里对一个位置的值加 $x$，把时间复杂度从 $O(n^2)$ 降到了 $O(1)$. 最后当所有的操作全部完成，只需要对差分矩阵做一次前缀和，即可恢复出原矩阵。

然而，目前我们只能对右下块的整体加操作进行转化，如何扩展才能转化任意一个子块呢？

我们考虑怎样用多个右下块组合表示一个子块。观察下图五：

我们把正准备进行 $\text{AddMatCell}$ 的目标子块在图中表示为 $OACB$. 我们约定 $\text{DR}(P)$ 表示以 $P$ 点为左上角的右下块。考虑 $\text{DR}(O)$，$\text{DR}(A)$，$\text{DR}(B)$，$\text{DR}(C)$ 和 $OACB$ 的关系。类似之前推导前缀和时用到的面积公式 $(1)$，我们有：

$$S_{OACB} = S_{\text{DR}(O)} - S_{\text{DR}(A)} - S_{\text{DR}(B)} + S_{\text{DR}(C)}$$

于是我们用四个右下块组合表示了一个子块，即对于子块 $OACB$ 的整体加 $x$ 操作，可以转化成：

1. 对于 $\text{DR}(O)$ 的整体加 $x$ 操作
2. 对于 $\text{DR}(A)$ 的整体减 $x$ 操作
3. 对于 $\text{DR}(B)$ 的整体减 $x$ 操作
4. 对于 $\text{DR}(C)$ 的整体加 $x$ 操作

这四个操作的结合。然后，我们利用对原矩阵右下块整体加操作等价于差分矩阵的单点加操作这一优良性质，再把这四个操作转化成 $O(1)$ 的单点加操作。

具体地，对于操作 $\text{AddSubMat}(\mathbf{A}, r_1, c_1, r_2, c_2, x)$，我们转化为：

1. $\text{AddMatCell}(\mathbf{D}, r_1, c_1, x)$
2. $\text{AddMatCell}(\mathbf{D}, r_1, c_2 + 1, -x)$
3. $\text{AddMatCell}(\mathbf{D}, r_2 + 1, c_1, -x)$
4. $\text{AddMatCell}(\mathbf{D}, r_2 + 1, c_2 + 1, x)$

如下图六所示：

我们可以对差分矩阵进行前缀和，检验这样的转化是否正确：

1° 当 $r_1 \leqslant r \leqslant r_2 \land c_1 \leqslant c \leqslant c_2$ 时，由于 $\mathbf{D}_{r_1, c_1}$ 被加上了 $x$，所以 $\mathbf{A}_{r, c}$ 都被加上了 $x$，如下图七；

2° 当 $r_1 \leqslant r \leqslant r_2 \land c > c_2$ 时，由于 $\mathbf{D}_{r_1, c_1}$ 被加上了 $x$，$\mathbf{D}_{r_1, c_2 + 1}$ 被减去了 $x$，所以两者抵消，$\mathbf{A}_{r, c}$ 不变，如下图八；

3° 当 $r > r_2 \land c_1 \leqslant c \leqslant c_2$ 时，由于 $\mathbf{D}_{r_1, c_1}$ 被加上了 $x$，$\mathbf{D}_{r_2 + 1, c_1}$ 被减去了 $x$，所以两者抵消，$\mathbf{A}_{r, c}$ 不变，如下图九；

3° 当 $r > r_2 \land c > c_2$ 时，四个操作点都被覆盖，相互抵消，所以 $\mathbf{A}_{r, c}$ 不变，如下图十；

严格的数学证明类似式 $(5)$ 的推导，这里不再赘述。