【转载】思考题：位运算加速（二）四毛子
2026-07-30 19:42:11
发布于：安徽
Method of four Russians
问题1. 有一个长为 的数列 ，其中相邻两个数之差必定是。 次询问一个区间 的最大值。
问题1.1. 请你给出一个 预处理， 查询的算法。
问题1.2. 请你给出一个 预处理， 查询，并且内存使用低于 的算法。（提示：考虑如何压位存储）
小明想了一个算法：将这个序列每 个元素分成一块。预处理每个块前缀最值、后缀最值；以及用区间最值数据结构维护整块组成的长为 的块序列的区间最值。对于跨块的查询，这样就可以 查询。对于单块内的查询，小明准备暴力预处理每个块的每个区间的最值。
问题1.3. 请你计算这个算法的时间、空间复杂度。
小明发现，当 特别小的时候，块内可能的大小关系种类数是有限的（并且小于 ）。因此小明考虑取一个足够小的 ，然后预处理所有长度 的块可能的大小关系，再对每个块进行查表，以减少预处理每个块的复杂度。
问题1.4. 请你计算出长为 的块的大小关系种类数上界，以及小明使用这个操作优化后的算法的时间、空间复杂度。
问题1.5. 请你取一个合适的 值，得到整体较优的复杂度。
像这样，分成若干小块，利用小块的可能取值种类数有限的性质预处理查表所有小块信息，再用原本的数据结构处理块间信息，可以优化复杂度。这个方法被称为Method of four Russians（“四毛子”算法）。
问题2. 尝试把上述算法推广到任意的区间最值（不限制相邻两个数之差必定是 ）。
位运算优化
Method of four Russians 是一个十分“笨重”的算法，长于从理论上发现问题复杂度可以优化，但是时空常数和代码都十分复杂。实际上，我们发现问题可以优化之后有一些更为简洁的办法。
（例如小块内放弃预处理直接暴力查询也可以节省空间和预处理复杂度，也就是类似每 个/层取一个关键点的方法）
问题3. 你有一棵 个点的二叉树，请你设计一个利用位运算 查询任意两点 的算法。预处理和内存不超过 。如果不限制二叉树呢？
问题4. 你有一个长 的序列，请你设计一个利用位运算 查询任意区间最大值的算法。预处理和内存不超过 。
问题5. 你有一个长 的括号序列，请你设计一个利用位运算 查询任意区间的括号消除剩余结果的算法。预处理和内存不超过 。
问题6. 利用这样的方法代替前述Method of four Russians算法中的块内查表部分，得到一个复杂度相同但实现更简单的算法。
答案
已经尽量把老师讲述的内容记录下来了，不敢想象我一个不会笛卡尔树的人能够完全停下来，虽然有部分没听懂。
四毛子概述
预处理 查询的算法
进行预处理上的优化：
对序列进行分块，块长 足够小的情况下，其内部情况数足够少，然后预处理所有块内前缀后缀的值，块之间进行 的预处理，块内小于 个级别的情况数（笛卡尔树）
问题1.1
表
int n,a[N],st[N][LogN];
void init(){
for(int i=1;i<=n;i++)st[i][0]=a[i];
for(int i=1;(1<<i)<=n;i++){
for(int j=1;j+(1<<i)-1<=n;j++){
st[j][i]=max(st[j][i-1],st[j+(1<<(i-1))][i-1]);
}
}
}
int query(int L,int R){
int k=log2(R-L+1);
return max(st[L][k],st[R-(1<<k)+1][k]);
}
此外，还可以利用线段树，递归到要把一个区间 要拆成两个区间的时候停止，下面如果继续递归相当于获取后缀区间和前缀区间的值，可以预处理，从而节省时间。该查询对于大区间近似 ，预处理每层 个数，共 层，时间复杂度 。
这个线段树的别名叫做猫树，因为发明人——陈俊坤——外号为猫。被评为 OI最烂算法，不推荐，纯科普。
问题1.2
数据结构，空间复杂度不太会高于时间复杂度，但也不会低于一般预处理的时间复杂度。
不过这道题限制了相邻位置差为 ，相邻位置间变化量小。
考虑给已知最值的区间两边增加部分元素，需要知道这一段的最值。
先进行差分，快速得到其中一个数的值，进一步得到序列前缀最值，
算出前缀最值之后利用压位的方式来存，每隔 位存储一个前缀最值，然后记录其差分，每一位至多两个 ，最后利用位运算快速还原其原来的值，利用 的内存存储原来的数组。（ 表示二进制位数）
由于 表相邻两个位置的最值差也是 ，也可以这样进行存储
问题1.3
利用问题1.1的 表进行处理的话，块间预处理是 ，每个块进行暴力时间复杂度为 ，因而预处理是 ，查询始终
可以通过求导来得出时间最短的时候 的取值，当然也可以利用“邪修大法”：直接令 。此处不进行后续无意义的计算。
问题1.4
一个区间的序列最值取决于其笛卡尔树， 个点的二叉树大概是对应项的卡特兰数的 ，总之就是近似
因而，预处理的时间复杂度为 ，其他几乎同上面计算，略
问题1.5
取 ，那么这里近似 的时间复杂度
注：这仅仅只是理论时间复杂度，且四毛子用脚指头想都知道很难写，一般只考虑其理论依据，除非要卡空间（问题1.2）
但是与其如问题1.2压位不如用其他方式，一般就是用四毛子来写，但只是理论说明其可行性。
问题2
对于一般序列，区间最值可以取决于笛卡尔树，因而可以贪心地在某种程度上进行值域压缩。
先求出笛卡尔树，单调栈扫一遍 求出，然后求树上两点 ，利用欧拉序进行求，两点间 应为两点遍历的欧拉遍历序列深度最小的点，且相邻节点深度之差为 ，因而转换成问题1.1的区间最值求即可。
时间复杂度还是近似 ， 种输入显然需要至少 个位来存储，不太可能低于这个时间复杂度。
问题3
对于二叉树，可以令向左边对应二进制一个 ，向右边对应二进制一个 ，而根节点的初始编号为 ，因此对于每个节点有唯一的二进制表示，然后异或两个节点，利用位运算求出最高位 ，对应的即是
不限制于二叉树的时候，可以构造虚点，以达到分散子节点的目的，保证加入虚点之后的树为一棵二叉树，然后同样方法求，最后还原。
问题4
可以建立笛卡尔树，但是有点麻烦。
对于一个数在笛卡尔树上的到根路径大致是从它最近一直跳上去，因而序列每个数都向左边最近的比它大的数连边，因而会得到一个后缀最大值（序列的单调栈），考虑查询 区间最大值，即 前缀的后缀最大值，跳跃找到在范围内的最大值。
注意到这个过程能够转换为 串的查询操作，可以把路径上的点设为 ，然后利用位运算操作。
问题5
消除结果一定是若干右括号接上若干左括号。
可以进行计算括号序列前缀和，然后查询区间最小值，也可以记这个序列的单调栈。
一个更简单的方式：用 串来记录前缀和折线，两个 串分别记录哪里 ，哪里 ，然后消除的时候当前位的 和下一位的 可以进行消除，因而合并两个串的时候可以用位运算模拟折线运算过程，合并消除。
总结：
可以用位运算判断能否模拟其结果，如果可以，那么能够进一步加速，进一步配合四毛子等算法来进行对暴力的优化
全部评论 2
这题我会。
1.1 考虑建一个 ST 表。
1.2 呃不会。
1.3 预处理 ；当 时，时间复杂度 ；当 时，时间复杂度 。
1.4 ；。
1.5 当 取 时，时间复杂度为 。- 考虑对原树建一棵笛卡尔树，转化成树上 LCA。而 LCA 是可以转化成 RMQ 问题的。
2026-07-30 来自 广东
0
有帮助，赞一个