四俄罗斯方法与字级并行

有限微块把许多次局部转移压成一个类型编号，字级并行则把许多独立布尔状态压进一个机器字；两者都先证明被打包的工作互不干扰，再用一次查表或字操作批量推进。加速来自这个可枚举或可并排的结构，不来自“使用了位运算”本身。

图中差分模式的二进制编码 1011 等于十进制11，所以查询写成 $T[11,l,r]$；右侧则把八位向量 $00001001$ 左移两位并与旧值求或，得到 $00101101$。

±1 RMQ 与 bitset DP ​

Euler 深度数组相邻差为 $\pm 1$。长度 $b$ 的微块减去首值后只由 $b-1$ 个正负步决定，类型数为 $2^{b-1}$；块内任意 RMQ 可按类型查表。这正是常数时间 RMQ理路线性预处理常数时间 RMQConstant-time RMQ · Farach-Colton–Bender RMQ · 线性 RMQ将一般静态 RMQ 归约为深度差为正负一的数组，再用微块类型查表与宏块稀疏表实现线性预处理、常数查询。的微结构。

考虑非负整数权重的0/1子集和，只保留和 $0,\dots ,W$，其中 $W\ge 0$。用 $W+1$ 个 bit 的向量 $R$ 表示可达性，初始只有 $R[0]=1$。读入权重 $0\le a\le W$ 后，以更新前的向量执行

并丢弃高于 $W$ 的位；权重超过 $W$ 时直接跳过。每个移位字最多从两个旧字取位，因而一次更新需要 $O(\lceil (W+1)/w\rceil )$ 个字操作。处理 $n\ge 1$ 个权重的总时间为 $O(n\lceil (W+1)/w\rceil )$，包括小于一个字的情形。若原地从低位向高位覆盖，可能把本轮刚生成的状态再次移位，相当于重复使用同一物品；应保留旧向量，或采用能保证读取旧值的高位到低位顺序。

失败边界 ​

表过大时缓存与预处理会吞掉收益；动态更新若改变微块类型，需要重新编码。理论 Word-RAM 的常数乘法、位提取不等同于任意现实 SIMD 指令，跨字移位和未对齐访问也不免费。未声明 $w$ 与允许操作时，声称“$w$ 位并行所以 $O(1)$”没有模型意义。

预处理复用与转移闭包 ​

应区分通用微表和依赖本次输入的表。$\pm 1$ RMQ 的相对答案只由差分类型和端点决定，能跨实例复用。布尔矩阵乘法中的行组合表则依赖具体矩阵。

例如把 $B$ 的行分成大小 $b$ 的组。对一组行 $B_{j_1,\ast },\dots ,B_{j_b,\ast }$，预计算每个选择掩码 $s\in \{0,1{\}}^b$ 的按位或：

计算 $AB$ 的一行时，$A$ 在对应列组的 bit 就是掩码，查表取出这些行的组合，再与其他组的结果求或。选择 $b$ 为适当对数尺度，可把逐个加入输入行的工作合并成按组处理；预处理、读取答案行与求或仍按实际长度计费。换一份 $B$，即使维数和掩码完全相同，$T_B[s]$ 也可能改变，因此该表须为新输入重新构建。经典传递闭包算法中的相关分块技巧同样需要核对每张表实际依赖的状态。

Broadword 算法还要防止相邻字段的进位串扰，常在字段间留 guard bits。把多个小整数装进一字后直接做普通加法，若未证明进位不会越界，就不是合法的“并行比较”。

参数为什么取对数级 ​

在 $\pm 1$ RMQ 中，微表的查询键应是 (type,l,r)：先减去块首深度，把正负差分编码成 type，再用块内端点查出相对最小位置，最后加回块起点。表保存的是相对位置而非绝对深度，所以同一类型才能跨不同块、不同实例复用。

块长还受查询字段编码限制。若 type、两个端点和答案不能在常数字内寻址，所谓“一次查表”本身就要多字运算；选择参数时必须同时核对类型数、端点表维度和地址字长，而不只是写 $b=\mathrm{\Theta }(\log n)$。

字级并行的另一条检查线是“一个字能否容纳所有字段与隔离位”。例如用位集做可达状态转移时，移位、按位与或在 $w$ 位字上一次推进 $w$ 个布尔状态；若状态跨越多个字，长度为 $L$ 的位向量成本应写成 $O(\lceil L/w\rceil )$ 个字操作（空向量单独处理），而不是无条件 $O(1)$。乘法、最高位定位或任意位抽取若参与算法，也必须列入 Word-RAM 的允许操作集合。