四俄罗斯方法与字级并行

两种共同思想 ​

四俄罗斯方法选微块长度 $b=\mathrm{\Theta }(\log n)$ 的适当常数倍，把块的有限类型与局部查询答案预计算成表；运行时把一整块归约为一次表查。字级并行则在字长 $w=\mathrm{\Omega }(\log n)$ 的Word-RAM公理库Word-RAM 模型Word RAM · Word-RAM model以 w 位机器字、常数时间随机访存和明确字级操作集分析算法的随机访问机模型。中，把多个布尔状态装入一字，用 AND、OR、shift、加法等受支持操作同时更新。前者以空间换时间，后者依赖机器字操作集合；二者不能只因都“按位”而视为同一定理。

表规模与复杂度 ​

若微块有 $2^{\mathrm{\Theta }(b)}$ 种类型，每型答案表为 $\mathrm{poly}(b)$，预处理大小是 $2^{\mathrm{\Theta }(b)}\mathrm{poly}(b)$。取 $b=c\log n$ 时必须让常数 $c$ 足够小，使该量为 $o(n)$；若表不能跨实例共享，它还要计入本次构建时间。

±1 RMQ 与 bitset DP ​

Euler 深度数组相邻差为 $\pm 1$。长度 $b$ 的微块减去首值后只由 $b-1$ 个正负步决定，类型数为 $2^{b-1}$；块内任意 RMQ 可按类型查表。这正是常数时间 RMQ 的微结构。

对子集和的布尔可达集合，用位向量 $R$ 表示，读入权重 $a$ 后执行

$$R\leftarrow R\vee (R\ll a),$$

一次字操作并行更新 $w$ 个状态，总时间从逐状态的 $O(nW)$ 变为 $O(nW/w)$ 个字操作。

失败边界 ​

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

预处理复用与转移闭包 ​

经典布尔矩阵传递闭包把矩阵切成宽度约 $\frac{1}{2}\log n$ 的块，为所有可能块模式预计算行更新。运行时一次表查替代逐位扫描，从立方时间中省下对数因子。这里表由 $n$ 和块规则决定，可在同规模实例间共享；若转移还依赖输入权重，类型数会膨胀，不能复用同一表。

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

参数为什么取对数级 ​

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

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

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

参考资料

• V. Arlazarov et al., On Economical Construction of the Transitive Closure of a Directed Graph, 1970.
• Donald Knuth, The Art of Computer Programming, Vol. 4A, bitwise techniques.
• Erik Demaine, MIT 6.851/6.854 Notes on Word-Level Parallelism.