前缀和

前缀和（$\text{Prefix Sum}$）。前缀，指的就是对于任何一个东西，从开头到某个位置连续的一端。比如对于一个数组，它的前几个元素，就组成了它的一个前缀。而和就是指的数学中的求和。

所以所谓的前缀和数组，就是我们去维护一个数组，而数组中的每一项，都代表了一段前缀的信息。

前缀和询问的应用

例题：叫号机的区间统计

通常，当我们遇到一个要解决的问题，是关于一段前缀，或者说关于一段连续的区间时，如果是区间的和，那么我们就可以用前缀和来优化这个暴力计算，当我们试图查询 [L,R] 这一段的区间和时，我们只需要使用 pre[R] - pre[L-1] 就可以快速得到某个区间的和。

当然，当我们把前缀和上升到一个思维的高度时，我们就会发现前缀和思想可以统计更多的东西。举个例子，对于“字符串相邻统计”这道题，如果我们想要统计一个区间内，有多少相邻项是符合给定条件的。那我们可以这样来应用前缀和：

 pre[i] = pre[i - 1] + (str[i - 1] == str[i - 2] ? 1 : 0);

这样一来我们就可以使用普通的前缀和查询区间和的方法，来统计更多种类的区间信息了。

练习题：

• 叫号机的区间统计
• 字符串相邻统计
• 双前缀求和
• AA的C
• 咖啡日统计

前缀和数组的应用

实际上，在拥有了前缀和数组之后，我们还可以对着前缀和数组维护出很多东西。

举个例子，如果我们有了前缀和数组，想要找一个长度为 k 的元素和最大的子区间，那么就可以在前缀和上对于每一个下标，固定去找一个长度为 k 的区间，就可以直接进行计算和更新了。

也有可能有些时候需要你求出某个子数组的最值，这种可能稍微麻烦一点，通常需要你根据你要统计的信息，固定一个右端点，去找左端点，例如在“最大子段和”中，我们需要对于每一个右端点，找一个能取到最优解的左端点，来进行答案的更新。

练习题：

• 最大子段和
• 大树下的阴凉处
• 定长区间总和
• 水壶
• 上课不要睡觉
• 走走停停

差分的应用

我们通常认为差分是一种和前缀和相反的操作。

当我们对一个数组做完差分操作得到了差分数组之后，如果我们再对差分数组做前缀操作，那么就能够还原出原数组。也正是基于这点，我们可以使用差分思想来快速更改区间加或减操作。

差分的最常见应用是区间修改。假设我们想要对于一个数组的 [L,R] 区间，进行加 x 操作，假设差分数组名为 diff，那么我们只需要对于 diff[L] + x，同时对 diff[R+1] - x，之后我们对差分数组进行前缀和操作，就可以得到原数组区间修改后的结果。

我们可以这样理解这个现象，当我们对某个位置进行操作的时候，根据前缀和的性质来说，这个操作会影响到这个位置后面的所有元素，那么如果我们如果想要这个影响在 L 位置开始，自然就要从 L 处开始修改。

但是这种修改会一直影响到最后，如果我们只想让这个影响存在于一个区间，那么最好的方法就是在 R+1 的位置做一个操作，把之前的操作抵消掉。这样一来从 R+1 开始的位置就不会受到这个影响了。于是我们在 $O(1)$ 的操作内完成了对于数组一段区间的修改。

练习题：

• 考试补分

• 最多涂色次数

• 买凤梨2

二维的前缀和与差分

理解了一维的前缀和与差分之后，我们自然可以把这个思想拓展到二维数组上，假设我们需要快速查询一个子矩阵的和，那么我们就可以维护一个二维前缀和的数组：

pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + a[i][j]

而在查询一个子矩形的时候，我们可以使用如下公式：

pre[x2][y2] - pre[x2][y1-1] - pre[x1-1][y2] + pre[x1-1][y1-1] 

于是我们就求出了 $[x_1\dots x_2]\times[y_1\dots y_2]$ 这个子矩形的和。

那么根据同样的原理，我们的差分操作也可以运用到二维数组上。

当我们要对 $[x_1\dots x_2]\times[y_1\dots y_2]$ 加上 $v$，首先我们需要对原矩阵进行差分操作：

diff[i][j] = a[i][j] − a[i−1][j] − a[i][j−1] + a[i−1][j−1].

之后对于每一个修改我们需要进行四个操作：

diff[x1][y1] += v;
diff[x1][y2+1] -= v;
diff[x2+1][y1] -= v;
diff[x2+1][y2+1] += v;

完成了所有的修改之后，我们只需要对这个差分数组进行二维前缀和操作还原出原来的矩阵就可以了。

直觉理解这个更改过程，每一次加法的本质都是在左上角 $+v$，右边界和下边界外 $-v$，在右下角之外 $+v$，这样就成功把子矩形外的影响抵消掉了。

练习题：

• 地毯覆盖
• 方形小区
• 求职

异或前缀和

在理解了前缀和的应用之后，其实我们还可以使用异或前缀和来进行区间的异或和统计。

原理是因为异或运算满足交换律和结合律，而且存在 x^x=0 的性质，所以我们可以使用：

pre[i] = pre[i-1] ^ a[i]

来统计出前缀异或数组，之后使用：

pre[r] ^ pre[l - 1]

就可以计算出 [l,r] 区间的异或和了。

练习题：

• 区间异或查询
• 和和异或和

前缀和后缀和

我们可以仿照前缀和的思想，对数组进行后缀和的处理：

suf[i] = suf[i + 1] + a[i]

有些时候我们会遇到一些题目，这些题目可能是对于某个点，把数组分成了两个部分，然后根据这两个区间来计算某些东西。这个时候常见的一个做法是同时维护前缀和数组和后缀和数组。对于每一个位置 i，直接使用 pre[i] 和 suf[i] 或相邻的前缀数组和后缀数组上的值来进行计算。

练习题：

• 向队长看齐
• 午枫的石子合并
• 弄丢作业