知识点

· · 个人记录

前缀和和差分

一维

前缀和：S_i = S_{i - 1} + A_i

差分：D_i = A_i - A_{i-1}

关系：逆运算

Ex：异或前缀和和异或差分的关系

例题 #1 求区间和

会发现 S[l,r] = S_r - S_{l-1}

例题 #2 语文成绩

在差分数组上给 D_i 加上一等价于 A_i,A_{i+1},\ldots,A_n 都加上 1 。

因此区间 [l,r] 加上 v 就是 D_l \leftarrow D_l + v,D_{r+1} \leftarrow D_{r + 1} - v

扩展：如果要做异或区间和和区间异或呢？

例题 #3 区间加等差数列

给定一个序列，q 次给一个区间加上等差数列，最后得到的序列是什么？

考虑区间加等差数列对差分数组的影响。

二维

如果想要求一个二维数组中一个矩阵内的所有数的和呢？

前缀和：表示这个点左上方的所有值的和

S_{i,j} = A_{i,j} + S_{i-1,j} + S_{i,j-1} - S_{i-1,j-1}

差分是什么？

D_{i,j} = A_{i,j} - A_{i - 1,j} - A_{i,j-1} + A_{i - 1,j - 1}

本质上是一种容斥

异或情况下的式子？

重要的点：当你确定了前缀和或差分数组，一定可以还原出原数组吗？

有时想要求出一个数组很难，但是求出差分或者前缀和数组更简单，会用到这个性质。

例题 #4 领地选择

直接求出二维前缀和计算每个矩阵内的和即可。

例题 #5 公路修建

这个就会用到前面所说的思想。

你需要让最终整个数组变成 0 很麻烦，但是在差分后将整个数组变成 0 非常简单，因为差分后区间加就是单点加。

因此差分后考虑即可。

例题 #6 区间和

还是刚刚的思想，想要确定 A_i 是非常麻烦的。

但是如果看成确定 S_n 的话，每次给出的信息就是 S_{l-1},S_r 之间互相可达。

如果连一条边，就变成了 0 能否走到 n 的问题。

例题 #7 特殊训练

首先按照需要的训练次数 c 排序。

然后枚举用了多少次 S 操作，会发现有一段后缀都是可以需要额外进行单独训练的，一段前缀是已经训练完成。

可以二分这个后缀的位置解决本题。但是更简单也更快的方法是用一个指针去维护这个位置。由于我们在从小到大枚举使用 S 的数量，因此这个指针的移动也是单调的。

树上的前缀和和差分

树上的前缀和、差分方式很多，每个都有不同的用处。

第一种：S_i = A_u + \sum_{v \in subtree_u} A_v

第二种：S_i = A_u + \sum_{v \in son_u} A_v ，对应链加操作

第三种：S_i = A_u + \sum_{v \in anc_u} A_v ，对应子树加操作

一类经典的前缀和问题

有这么一类问题非常经典：在数轴上有若干个点，选择一个点它向所有点的距离和尽量小。

我们不考虑数学上的结论，这是因为这个题可以有很多变式，变式可能就没有结论了。首先选择的点肯定是这些点中的一个，否则一定可以调整过去。那么枚举这个点 x 后，距离和就是：

\sum_{x_i < x} (x-x_i) + \sum_{x_i > x} (x_i - x)

这个值可以拆开，会得到一个前缀和的形式。因此给所有 x 排序后前缀和即可解决问题。

二分和双指针

二分

二分是什么？

单调的东西求分界点。

二分的重要条件是单调，也就是前半部分可以，后半部分不可以。

单调性一般有两种满足方法：

还存在一种经典的二分：有两个问题，尽量合理地安排它们，也就是让两边尽量接近。

偷懒方法：lower_bound,upper_bound

例题 #1 数数

首先，显然询问和数组顺序无关，因此先给整个数组排序。

然后每次询问就是找到序列中小于等于 x 和大于 x 的分界点，并且这个性质是单调的。

例题 #2 A-B 数对

还是和顺序无关，因此可以排序一下。

然后可以枚举 B ，就只需要找出有多少正好等于 B+C 的值的数量了。

这个数量可以通过二分得到。

例题 #3 Sisyphus

施展魔法总是从大到小施展，这样才能保证西西弗斯亏的距离最大。

当确定了施展魔法的个数时，可以计算出西西弗斯需要走的总距离，因此就可以求出他走完全程所需要的时间。

走的时间显然是关于施展的魔法数单增的，因此可以二分施展多少魔法可以拖他这么久。

例题 #4 区间

最大化最小值和最小化最大值是非常非常经典的二分题模型。

看到这两个条件就要想到二分。

主要是二分完了就变成了一个“所有数都必须大于等于/小于等于“的判定性问题。

这种问题往往是比较容易判断的。

例题 #5 中位数

给出一个两个序列，两个序列均为有序数组，每次有两种操作：

考虑前一半小在两个序列分别占了多少个。

如果二分在第一个序列占了多少个，假设是 x ，那么只需要判断 A_x > B_{k - x + 1} 即可。

这样可以二分出中位数在第一个序列占了多少个数，实现单 \log 。

例题 #6 Median Pyramid

给出一个 n 层金字塔，每次会把一个位置底下的三个位置的中位数给放到当前位置，问最后最上面是多少。

简单版：n \le 5000 。

二分答案后对中位数的影响是非常大的，会非常好做。

例题 #8 旅行

然后将所有点按 w 排序，接下来考虑二分答案。

可以二分最后选取的城市在排序后序列中的位置，然后相当于判断后缀之中是否存在距离超过当前二分的权值的点。

这个二分本质上就是找到 w 和距离的一个“平衡点”。

怎么判断距离？我们知道 |x_1-x_0| + |y_1-y_0| = \max(x_1-x_0+y_1-y_0,x_0-x_1+y_1-y_0,\ldots) ，直接把绝对值拆成四个最大值。

然后对每个情况分别统计后缀最大值即可。

双指针

有时单调问题可以不需要二分来解决，利用上次复杂度分析所分析到的方法。

双指针能解决的问题二分几乎都能解决，但是双指针更快也更好写，本质就是如果二分需要查询到的位置也是单调增加的，那么就可以用双指针解决。

我们可以回忆一下归并排序的过程，最后合并的过程就是一个简单的双指针。

例题 #1 数数

看起来每次查询到的维护并不是单调增加的，怎么应用双指针？

可以给所有查询按照 x 从小到大排序，那么小于等于 x 的最大的数的位置就是不断增加的了。

这样就可以用一个指针去扫这个位置，而不需要枚举了。

例题 #2 A-B 数对

可以重新解决这个问题，可以维护一个指针来表示 B+C 的位置，随着 B 的增加这个指针也是单增的。

维护两个指针，分别表示第一个和最后一个 B+C 的位置，这样就可以用双指针扫过去了。

扩展

*扩展 #1 最大化斜率

最大化最小值的一半方法就是二分。可以二分这个斜率，相当于选出一些点，这些点两两斜率都大于等于这个值。

如果二分的斜率是 k ，那么对于每个点都可以画一条 kx + b 的直线，问题等价于选一个点后只能选直线上方的后面点，也就是说选出 b 的最长上升子序列即可。

*扩展 #2 位运算

有另一种特殊的二分策略，类似于倍增，是从高到低确定答案的每一个位，常用于位运算相关的问题。

从高到低考虑每一位，尝试这一位是否可以为 1 ，如果可以就放 1 考虑下一位，否则就放 0 。

如果想要尝试这一位是否可以放 1 ，只需要贪心考虑所有分界点，满足分界的每个段内部都在高位和枚举的值一样，看看最后分出的子段数是否大于等于 k 即可。

基础数据结构

点不进去吧

测试 题解