前缀和与差分

前缀和

前缀和是指某序列的前n项和，可以把它理解为数学上的数列的前n项和。

假定$a_1,a_2,a_3,a_4…..a_n$为我们的原数组。给定m个$l,r$，要求求出$l$到$r$的区间和。

直接枚举一遍$l,r$进行求解的时间复杂度是$O(n*m)$，对于时间复杂度较严格的题，这样的做法是不可取的。

现在，假定有一个数组$p_1,p_2,p_3…p_n$，其中：

• $p_1 = a_1$
• $p_2 = a_1 + a_2$
• $p_3 = a_1 + a_2 + a_3$
• $p_4 = a_1 + a_2 + a_3 + a_4$
• …
• $p_n = a_1 + a_2 + … + a_{n-1} + a_n$

我们可以通过这个数组轻松得到$l$到$r$的区间和：
$$\text{sum}(l,r) = p[r] - p[l - 1]$$

通过这个公式，我们可以快速算出一段区间的和，时间复杂度是$O(1)$。

$p$数组的构建过程称之为预处理，需要的时间是$a$数组的长度$n$。因此，预处理的时间复杂度为$O(n)$。加上m次查询，总复杂度变为$O(n+m)$，大大提高了运行效率。

差分

差分是一种用于处理序列变化的技术，特别适用于需要频繁对区间进行修改的场景。

考虑一个序列 $a_1, a_2, a_3, \ldots, a_n$。我们引入差分数组 $d_1, d_2, d_3, \ldots, d_n$，其中 $d_i = a_i - a_{i-1}$。

• $d_1 = a_1$
• $d_2 = a_2 - a_1$
• $d_3 = a_3 - a_2$
• …
• $d_n = a_n - a_{n-1}$

接下来，通过对差分数组进行前缀和操作，得到原始数组 $a$。差分数组的前缀和恰好是原始数组：

• $a_1 = d_1$
• $a_2 = d_1 + d_2$
• $a_3 = d_1 + d_2 + d_3$

通过差分数组，可以快速进行区间修改和查询。对于区间 $[l, r]$ 的增量操作（假设增量值为 $c$），我们可以将差分数组进行如下修改：
$$
\begin{aligned}
d_l += c ,\
d_{r+1} -= c \
\end{aligned}
$$

因为差分做前缀和是原数组，所以我们对$d_i$进行操作的话，在原数组当中，其实就是对$a_i$到$a_n$进行了一次操作。

要想实现区间操作$[l,r] + c$就在$l$的位置加上$c$,之后在$r + 1$的位置减去c，这样差分数组在做前缀和操作之后，即把原数组的$[l,r]$进行了一个$+c$的操作。

通过差分数组 $d$，可以高效进行区间的增减操作。差分数组的构建和操作过程是一种预处理，其时间复杂度为 $O(n)$。随后对 $m$ 个查询操作的时间复杂度为 $O(m)$。总体而言，差分技巧能够在降低时间复杂度的同时，高效地处理区间操作。

值得注意的是，前缀和和差分这两种操作都是离线操作，也就是说不能边修改原数组的值，边进行前缀和和差分。

二维前缀和

构建思路

假设有一个二维数组 $a_{i,j}$，表示矩阵中的元素。我们想要在矩阵中快速计算某个子区域的和。为了实现这一目标，我们引入了二维前缀和数组 $p_{i,j}$。

公式推导

构建过程的关键在于理解 $p_{i,j}$ 如何由原始数组 $a_{i,j}$ 推导而来。我们使用以下公式：

$$
p_{i,j} = a_{i,j} + p_{i-1,j} + p_{i,j-1} - p_{i-1,j-1}
$$

这个公式直观地描述了 $p_{i,j}$ 是由当前元素 $a_{i,j}$ 加上其上方、左方的前缀和，再减去左上角的前缀和得到的。

性质

通过构建二维前缀和数组，我们可以在 $O(1)$ 的时间内计算任意矩阵子区域的和。这种预处理大大提高了区域和的计算效率。

二维差分

构建思路

二维差分用于处理对二维数组中区域进行频繁修改的情况。我们引入了二维差分数组 $d_{i,j}$。

公式推导

构建过程的关键在于理解 $d_{i,j}$ 如何由原始数组 $a_{i,j}$ 推导而来。我们使用以下公式：

$$
d_{i,j} = a_{i,j} - a_{i-1,j} - a_{i,j-1} + a_{i-1,j-1}
$$

这个公式描述了 $d_{i,j}$ 是当前元素 $a_{i,j}$ 与其上方、左方以及左上角元素之间的变化量。

区域增减操作

通过修改二维差分数组，我们可以在 $O(1)$ 的时间内进行矩阵子区域的增减操作。对于矩阵子区域 $[x_1, y_1, x_2, y_2]$ 的增量操作（假设增量值为 $c$），我们可以将二维差分数组进行如下修改：

$$
\begin{aligned}
d_{x_1, y_1} += c ,\
d_{x_2+1, y_1} -= c ,\
d_{x_1, y_2+1} -= c ,\
d_{x_2+1, y_2+1} += c ,\
\end{aligned}
$$

差分数组的还原

通过对二维差分数组进行前缀和操作，得到原始数组 $a$。差分数组的前缀和即为原始数组：

$$
\begin{aligned}
a_{i,j} &= d_{i,j} + a_{i-1,j} + a_{i,j-1} - a_{i-1,j-1}
\end{aligned}
$$

通过结合二维前缀和和二维差分，我们可以高效地处理二维矩阵区域的计算和修改。

tips:

当然还有三维，不过一般一维就够了，二维的题也不多,除了上面这些方法，还可以使用树状数组和线段树来求前缀和和差分。