位运算技术（整合修订版）

· · 算法·理论

upd on 25.5.24：提交了本文。我感觉玩 WRM 很有意思，但莫得前途。

定义

位运算，加法，乘法，除法和一些内置指令时间复杂度 O(1)。

这个其实很有用。 比如 [NOI Online #3 入门组] 买表，直接二进制优化做是带个 $\log$ 的，但是 bitset 优化能把 $\log$ 除掉。 ### 内容 * ACP-I * In a trap * RMQ * 树上线性并查集 * 拓展（LA） * 异或序列 * 第七学区 [题单](https://www.luogu.com.cn/training/258452#information)。 大部分都是之前我 blog 里面的内容。 ### ACP-I 很有趣的题目，用到的技巧都很简单，建议自己做一下。 加法其实有更快的实现方法。 ### In a Trap $O(n\sqrt n)$ 做法并没有用什么很奇特的位运算技术，但是还是有点意思的。 预处理对于每个点上方 $2^{\frac {\log n} 2}$ 个点，$\forall x\in [0,2^{\frac {\log n} 2})$ 求出 $x$ 的最优匹配。这样每次向上跳 $2^{\frac {\log n} 2}$ 个点是不影响后 $\frac {\log n} 2$ 位的。 总而言之就是 $O(\sqrt n)$ 预处理。 我们预处理一个东西：每个 $\frac {\log n} 2$位前缀对应的后缀的 $\max$，然后在上面建 01trie，这个显然是 $O(\sqrt n)$ 的。 然后要对 $\forall x\in [0,2^{\frac {\log n} 2})$ 求出 $x$ 的最优匹配。 按位考虑每一位。 * 如果这里同时有 $0,1$，那么我们把所有 $0$ 都去匹配 $1$，所有 $1$ 去匹配 $0$ 即可。 * 如果这里只有 $0/1$。那么所有的数都只能匹配这个 $0/1$。 用一个 dfs 维护上面的过程。会发现填到最后有一些位是确定的，其他的不确定。 先把确定的位压起来，考虑不确定的位。 会发现如果有 $x$ 个不确定的位，把这些位置用栈存起来，可以直接 $O(2^x)$ 再用一个 dfs 求出对应的每个数。这里总时间复杂度 $O(\sqrt n)$，因为保证了每个数只被求一次。 比较抽象，可以看 [CF 评测记录](https://codeforces.com/contest/840/submission/175229652)。 ### RMQ ~~不会还有人 RMQ 写四毛子吧，这部分都多久以前的东西了~~ 以最大值为例。 把序列分块，块长 $\Theta(w)$，对每块的最大值建 ST 表。 中间的整块直接 ST 表，时间复杂度 $O(\dfrac n w\log(\dfrac n w))=O(n)$。 那么考虑散块，$l,r$ 同块的情形。 考虑单调栈。举例子： ``` a:1 3 5 2 4 1:1 2:2 3:3 4:3 4 5:3 5 ``` 现在问题来了，如何用上面的单调栈求出 $[2,4]$ 的最大值？ 我们找到第 $4$ 时刻的单调栈，第一个 $\ge 2$ 的数 $p_i=3$，$a_{p_i}=5$ 即为答案。 一般的，对于区间 $[l,r]$，我们找到 $r$ 时刻的单调栈中第一个 $\ge l$ 的 $p_i$，$a_{p_i}$ 即为答案。这个是显然的。 我们在块内使用这个算法即可。 将每个的单调栈压到一个 word 里面。然后直接位运算求出第一个 $\ge l$ 的位置。 具体的，我们使用 `l+__builtin_ctz(st[r]>>l)`。 解释一下，`__builtin_ctz(x)` 表示求 $x$ 的二进制表示从末尾开始 $0$ 的个数，`st` 表示状态压缩的单调栈数组。`st[r]>>l` 将 $[0\dots l-1]$ 的二进制位去除，只保留 $[l\dots r]$ 的二进制位。设要求出来的数为 $v$，则末尾应当有 $v-l$ 个 $0$，加上 $l$ 后正确的求出了 $v$。 ~~为数不多的~~[代码实现。](https://www.luogu.com.cn/paste/xynn9r9k) 用这个来做 LCA 其实很方便，我封装了一个 dfn 序的 $O(n)-O(1)$ LCA，[代码实现。](https://www.luogu.com.cn/blog/203623/post-lca) ### Freezing with Style 类似的应用。（希望没假） 二分答案 $O(n)$ 后求树上链长在 $[l,r]$ 内的链的和的最大值。 考虑长链剖分。每次从下往上扫一条长链，每次把短链求答案之后合并上来。 那么需要一个数据结构，支持： * 全局加 * 定长区间最大值 * 往前段加一个数 * 将前缀的若干个数变大，“若干个数”数量总和 $O(n)

显然全局加没用。定长区间最大值就直接按定长分块，每次查询分成块的前缀和后缀。前面在更新的非整块显然平凡。每次将前缀的若干个数变大可以说是对某个块的前缀操作。

发现对每个块的后缀维护也平凡。实际上只剩下：

按 \log n 分块。对 2\sim k 块维护 ST 表。那么对 2\sim k 块的维护直接重构、在 ST 表上 O(\log n) 修改均摊复杂度显然是对的。

考虑第一块，维护所有前缀最大值的位置。每次修改的时候加入一些前缀最大值，删掉一些值，均摊复杂度对的。然后用一个 word 维护所有前缀最大值的位置，查询求出这个前缀最后一个前缀最大值即可。

所以时间复杂度 O(n\log n)。

树上线性并查集

题意：并查集，给一棵树，每次合并操作只会是树边。

之前看到的都是四毛子，其实感觉 not practical。

对树按照 B=\Theta(\sqrt w) top cluster 分块，维护块间连通性，即解决收缩树上的上述问题。

这部分用并查集维护是 O(n+m) 的。

对于块内查询，问题是规模为 B 的树上的上述问题。这里我们希望查询点的连通块中的深度最小的点。

然后考虑一下有没有和界点联通。

每个块维护一个 word，对于每个界点，维护它到根的路径上的点是否与其父亲合并，然后就是查第一个没有与父亲合并的点。

这里需要 B^2=\Theta(w) 个 bit，可以用一个 word 存下。

再对每个点维护这个点与父亲合并后对 word 的影响，这个可以进行一次 dfs，叶结点平凡，非叶节点就是他所有儿子左移一位之后或起来。

查询可以用一些简单的位运算和内置指令完成。

其实这里有个问题，就是你知道了答案在你的到根的链的某个位置，你还要知道这个祖先的编号。

这个可以将树三度化，初始联通虚点，然后每个点存个 word 表示从根到该点走过左右儿子的信息。

然后截取出从根走到这个祖先经过的左右儿子的信息，维护一下这类信息和树上结点编号的映射即可。

拓展

这个算法其实有一定劣势。

举例子：LA，即树上 k 级祖先。

离线有一个简单算法，所以考虑在线。

首先有一个 O(p\log n)-O(1) 的算法，p 是叶子数量。

其实就是把查询转为叶子上的查询。

将子树大小 \le B 的截取出来，然后 O(1) 解决这部分。

现在剩下的只有 O(\dfrac n B) 个叶子，可以调用上面的算法。

好了问题在于 B 的取值，首先 B=\Omega(\log n)。

显然一棵树可以用括号序描述，所以规模为 B 的树立刻得到卡特兰数的上界。

所以四毛子可以取 B=\dfrac {\log n} 4 然后就解决了。

然后考虑一下位运算怎么搞。

改一下上面树上线性并查集的做法，每个点用 \log B 个 bit 表示，就是重标号一下，然后把祖先链压在 word 里。

维护一下重标号与原标号的映射，然后就可以快速算出每个点的 k 级祖先。

那么每个点要 B\log B 个 bit，所以要求块长 O(\dfrac w {\log w})。

出事了。

根本原因是位运算只能通过一些简单的操作，所以没法在括号序上操作。

考虑通用技巧迭代分块。

就是说考虑按块长为 \Theta(\log n) 分块（按上面的说法，截取子树），然后考虑规模为 \Theta(\log n) 的问题。

然后按块长为 \Theta(\sqrt w) 分块。每块的时间复杂度是 O(\dfrac {\log n} {\sqrt w}\log \log n)，总的是 O(n) 的。

一般来说，如果可以 O(nf(n))-O(1) 地处理一个问题，并且可以进行某种分块，就可以按块长为 \Theta(f(n)) 分块，然后解决规模为 n'=\Theta(f(n)) 的问题。那么就可以 O(nf^*(n))-O(f^*(n)) 地解决。

多次使用一般可以做到反阿克曼函数。

如果又存在算法对于 n'\le B 的情形可以 O(n')-O(1) 解决，那么迭代次数就会更少一些，是有可能 O(n)-O(1) 解决的。

异或序列

题意：给你一个序列，求其所有子区间的按位异或和的和。

考虑这个问题：

给出若干个整数。w 为字长，\forall i\in [0,w)，求出这些整数的二进制表示在第 i 位有多少个 1。

法一：位分块

将整数每 k=\Theta(\log n) 分一块，分成常数块。

所以我们只用处理常数次值域为 m=2^k 的问题。即每个数 \in [0,m)。

考虑 01trie 结构。具体的，我们对于每个整数 x，在 t_{x+m} 上计数一次，然后进行递推 t_w =t_{2w}+t_{2w+1}。

最终对每层计数一次。ans_i =\sum _{x \bmod 2=1 \land x\in [2^{k-i},2^{k-i+1})} t_x。

这样我们做到了 O(m) 处理这个问题。

注意：w=\Omega(\log n)，时间复杂度是 O(nw/\log n)，并非线性。同样的，我们也不能认为基数排序的复杂度是线性。

想起一个经典问题：链最大值如何 O(n)-O(1)？先迭代几次四毛子之后要找映射，所以不得不排序。这里需要利用 atomic heap 做到小规模的线性排序。

代码实现。

法二：分治

设计 01 计数数组 a，a_{i,j}(i\in [1,\log n], j\in [1,w]) 表示第 j 位的 1 的数量的二进制表示的第 i 位。就是把一般的计数数组转置了。

说人话，举个栗子：

考虑分治。处理两个规模为 $\dfrac n 2$ 的子问题后合并左右的计数数组 $a,b$，设其得到 $c$。 考虑这里合并的本质：并行计算 $w$ 个二进制加法。 我们对计数数组的第二维压位，因为 $j\in [1,w]$ 所以每个第二维均可以压进一个 word 里面。所以计数器维护了 $O(\log n)$ 个 word。 同理，每一位是否进位也可以压进一个 word 里，还有一个原因就是这里至多进位一次，设其为 $t$。 计算 $c_i$：显然为 $t \oplus a_i \oplus b_i$。 计算 $t$：即判断两次加法的过程中是否有任何一个进位了。即 $(a_i \land b_i)|((a_i \oplus b_i)\land t)$。 每次合并的时间复杂度为 $O(\log n)$。时间复杂度即 $T(n)=2T(\dfrac n 2)+O(\log n)$。 $\log n=o(n)$，根据主定理，时间复杂度线性。 [代码实现](https://www.luogu.com.cn/paste/zf0ov9fj)。 ### 第七学区 题意：给你一个序列，求其所有子区间的按位或和的和。 这个应该没办法用位分块近线性做。 考虑求出每一位的答案。即保留这一位后形成的 $01$ 序列有多少个区间中至少有一个 $1$。思路同上。 一个经典的思想是分治。用上面计数器合并的方法。 考虑这里合并的本质：并行计算 $w$ 个二进制加法/乘法。加法已经描述过，考虑乘法，暴力乘法即可。本质上是做 $O(\log n)$ 次加法。 合并时间复杂度 $O(\log ^2 n)$。 每次合并调用 $O(1)$ 次加法和乘法。 每次合并的时间复杂度为 $O(\log n)$。时间复杂度即 $T(n)=2T(\dfrac n 2)+O(\log ^2n)$。 $\log ^2 n=o(n)$，根据主定理，时间复杂度线性。 具体实现的时候不要朴素分治，要二进制分组，这样空间复杂度能做到 $O(\log ^2 n)$。 ### 总结 位运算 nb。