二进制拆分技术，万物皆可除以 w！

Eterna · 2026-03-12 13:23:27 · 算法·理论

以下 w=64 表示字长。

其实是一个有些古老的技巧，算是出自 P8569 吧。不太普及，但是感觉可以放在很多数据结构题上骗分。

对于若干长度为 n、值域为 [0,V]\cap N 的序列，以下为说明方便先有两个序列 \{a\},\{b\}。

利用这个技巧，我们可以在单次 \mathcal{O}\left(\dfrac{n \log V}{w}\right) 的时间复杂度内做到以下操作：

1. 区间 a_i \gets a_i+v。
2. 区间 a_i \gets \min\{a_i,v\}/\max\{a_i,v\}。
3. 区间 a_i \gets a_i \operatorname{xor} v/a_i \operatorname{and} v/a_i \operatorname{or} v
4. 区间 a_i \gets a_i+b_i。与前面配合可以维护历史版本和。
5. 区间 a_i \gets \min\{a_i,b_i\}/\max\{a_i,b_i\}。与前面配合可以维护历史最值。
6. 区间除二的幂，即 a_i \gets \lfloor \dfrac{a_i}{2^k} \rfloor。
7. 查询区间和/\max/\min/\operatorname{xor}/\operatorname{and}/\operatorname{or}。
8. 查询区间有几个数 \le v。
9. 查询区间 \text{popcount}(a_i) 之和。

可以说想到什么有什么。常数很小，而且这些操作其实可以共存！实测尤其在许多类似扫描线的题上是比较有用的。

为方便讲解，以下我们将 n \gets w，对于 n 更大的情况就处理 \dfrac{n}{w} 次即可。

我们将每个 a_i 二进制拆分，写成下图的格式：

显然，这是一个 \lfloor\log V\rfloor \times w 的 01 矩阵，其中竖着的那一维长度为 \lfloor\log V\rfloor。

事实上，我们直接存储 a_i 的值相当于按蓝色框的方向压位。

但是这样的压位方式比较浪费，因为一个整形压位可以最多压 w 位，但是我们只压了 \lfloor\log V\rfloor 位。

不妨按照绿色框的方向压位，这样一定可以压满 w 位。

这样我们就得到了一个长度为 \lfloor\log V\rfloor 的数组 \{s\}，s_i 描述了 a 上有哪些位置的第 i 位为 1。

然后我会讲几个操作的做法：

• 整体加 v。

  将 v 二进制拆分为 [v_0,v_1,\ldots ,v_{\lfloor\log V\rfloor}]。若 v 的第 i 位为 1，v_i=2^{w}-1，也就是全集。否则为 0。从低位向高位枚举，同时维护一个整数 p，表示每个位置到当前位是否存在进位。

  显然每一位有 s_i \gets s_i \operatorname{xor} v_i \operatorname{xor} p，而 p \gets (s_i \operatorname{and} v_i)\operatorname{or}\big[(s_i \operatorname{xor} v_i)\operatorname{and} p\big ]。

  可以十分容易的类比到区间加、上面的操作 4（对 b 也做二进制拆分在某些时候是不可接受的）。

  以下是一份维护操作 4 的代码。

#define vc vector<int>
inline vc merge(vc x,vc y){
    if(x.size()<y.size())swap(x,y);int p=0,P,i=0;
    for(;i<y.size();p=P,++i)
        P=(x[i]&y[i])|((x[i]^y[i])&p),x[i]^=(y[i]^p);
    for(;i<x.size();p=P,++i)P=x[i]&p,x[i]^=p;
    if(p)x.push_back(p);return x;
}

• 整体对 v 取 \max。

  将 v 二进制拆分为 [v_0,v_1,\ldots ,v_{\lfloor\log V\rfloor}]。若 v 的第 i 位为 1，v_i=2^{w}-1，也就是全集。否则为 0。从高位向低位枚举，维护一个整数 p，表示每个位置是否在前面的位中与 v 一样。还有一个整数 q 表示每个位置是否 < v。

  显然每一位有 q \gets q\operatorname{or}\big [(s_i \operatorname{xor} v_i)\operatorname{and} v_i \operatorname{and} p\big ],p \gets \big [*(s_i \operatorname{xor} v_i)\big ] \operatorname{and} p。其中我们用 *x 表示 x 取反的结果。

  最后 q 为 1 的位 j 上，对应的 a_j < v。将它们赋值为 v 即可。

  可以十分容易的类比到上面的操作 5、操作 8。

如果你理解了这两个，其他的操作相信你也会做了。

下表是用这个技巧维护区间取 \max 与直接暴力的效率对比（n,V 同阶）：