Skip to main content

倍增

Summary

倍增（Binary Lifting）预处理以 2 的整次幂为步长的状态，再把任意目标步数按二进制拆成若干 2 的幂之和，逐段跳跃合并出答案。设 f(i,x) 表示从状态 x 走 2 的 i 次方步后的结果，递推式为 f(i,x)=f(i-1,f(i-1,x))，预处理复杂度 O(nlogn)，单次查询 O(logn)。这套思想是 ST 表与最近公共祖先 LCA 的基础，也用于求树上第 k 级祖先一类可倍增合并的问题。

参考资料​

简介​

倍增（Binary Lifting）的核心思想是：预处理以 22 的整次幂为步长的状态，然后将任意目标分解为若干 22 的幂次之和，逐段合并得到答案。这利用了「任意非负整数均可用二进制表示」这一性质。

预处理阶段，设 f(i,x)f(i,x) 表示从状态 xx 走 2i2^i 步后的结果，则递推关系为：

f(i,x)=f(i−1,f(i−1,x))f(i,x)=f(i-1,f(i-1,x))

预处理复杂度为 O(nlog⁡n)O(n\log n)，每次查询 O(log⁡n)O(\log n)。

应用​

详见 ST 表。

详见 最近公共祖先（LCA）。

例题​

洛谷 P3865 【模板】ST 表 && RMQ 问题

给定一个长度为 NN 的数列，和 MM 次询问，求出每一次询问的区间内数字的最大值。

洛谷 P3379 【模板】最近公共祖先（LCA）

给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。