Binary Lifting
倍增在做什么
**倍增(Binary Lifting)**的核心思想:
预处理出"跳 步"的信息,之后任意 步都拆成二进制,用 次跳跃拼出来。
把 次操作压缩成 次。
成立的前提:操作满足结合性 / 可合并性——"跳 步" = "跳 步" 再 "跳 步"。
跳 13 步 = 跳 8 步 + 跳 4 步 + 跳 1 步
= 3 次操作(而不是 13 次)通用形式
定义状态 up[k][x]:从 x 出发,做 次操作后到达的位置(或得到的结果)。
递推:
up[0][x] = 一次操作的结果(直接算)
up[1][x] = up[0][ up[0][x] ] ← 两次
up[2][x] = up[1][ up[1][x] ] ← 四次
...空间:。预处理时间:。查询:。
应用一:快速幂
最纯粹的倍增(虽然通常不叫这个名字):
long long qpow(long long a, long long n, long long mod) {
long long res = 1 % mod;
a %= mod;
while (n) {
if (n & 1) res = __int128(res) * a % mod; // __int128 防溢出
a = __int128(a) * a % mod; // a = a^2, a^4, a^8, ...
n >>= 1;
}
return res;
}为什么是:a 序列是,第 位是;n 的二进制第 位为 1 就乘上对应的项。
注意溢出:mod 接近 时,res * a 会超 long long()。用 __int128 或先取模再乘。
矩阵快速幂
线性递推式(如斐波那契)可以写成矩阵幂:
配合快速幂, 求第 项(而不是 递推)。
通用化:任何 阶线性递推 都能写成 矩阵的幂 →。
应用二:ST 表(RMQ)
问题:静态数组,多次查询区间 的最大值,无修改。
思路:st[k][i] = 从 开始、长度 的区间的最大值。
const int N = 1e5 + 5, K = 17; // 2^17 > 1e5
int st[K][N], lg[N];
void build(const vector<int>& a) {
int n = a.size();
lg[1] = 0;
for (int i = 2; i <= n; i++) lg[i] = lg[i >> 1] + 1; // 预处理 log
for (int i = 1; i <= n; i++) st[0][i] = a[i - 1];
for (int k = 1; (1 << k) <= n; k++)
for (int i = 1; i + (1 << k) - 1 <= n; i++)
st[k][i] = max(st[k - 1][i], st[k - 1][i + (1 << (k - 1))]);
}
// 查询 [l, r](1-indexed)
int query(int l, int r) {
int k = lg[r - l + 1];
return max(st[k][l], st[k][r - (1 << k) + 1]);
}查询的原理:用两个长度 的区间覆盖,允许重叠。
[l r]
[ 2^k ]
[ 2^k ]
↑ 重叠不影响 max/min 的正确性为什么允许重叠:因为 和 是幂等的(重复计算不改变结果)。所以 ST 表只适用于可重复贡献的问题(max、min、gcd、按位与/或),不能用于求和(会重复计算重叠部分)。
| 问题类型 | 能否用 ST 表 |
|---|---|
| 区间 max / min | ✓ |
| 区间 gcd | ✓ |
| 区间按位与 / 或 | ✓ |
| 区间和 | ✗(用前缀和) |
复杂度:预处理,查询,空间。
对比线段树:ST 表查询 更快,但不支持修改。静态 RMQ 用 ST 表,动态用线段树。
应用三:树上倍增求 LCA
LCA(Lowest Common Ancestor):两个节点最近的公共祖先。
1
/ \
2 3
/ \ \
4 5 6
/
7
LCA(7, 5) = 2
LCA(4, 6) = 1
LCA(4, 5) = 2预处理
up[k][u] = 节点 的第 个祖先。
const int N = 1e5 + 5, LOG = 17;
int up[LOG][N], depth[N];
vector<int> g[N];
void dfs(int u, int p) {
up[0][u] = p;
for (int k = 1; k < LOG; k++)
up[k][u] = up[k - 1][up[k - 1][u]]; // 2^k 祖先 = 2^(k-1) 祖先的 2^(k-1) 祖先
depth[u] = depth[p] + 1;
for (int v : g[u]) if (v != p) dfs(v, u);
}
// 根的父设为自己(这样"跳过了头"会回到根,不会越界)
void init(int root = 1) {
depth[0] = -1; // 让 root 的 depth 为 0
dfs(root, 0);
up[0][root] = root;
for (int k = 1; k < LOG; k++) up[k][root] = root;
}查询
1. 把较深的节点往上提,直到两者深度相同
2. 两个节点同时往上跳,从大到小试 2^k,能跳就跳(跳了还不相同才跳)
3. 最终停在 LCA 的两个子节点,答案就是它们的父int lca(int u, int v) {
if (depth[u] < depth[v]) swap(u, v);
// 1. 对齐深度:把 u 上提 depth[u] - depth[v]
int diff = depth[u] - depth[v];
for (int k = 0; k < LOG; k++)
if (diff & (1 << k)) u = up[k][u];
if (u == v) return u; // v 本来就是 u 的祖先
// 2. 同时上跳
for (int k = LOG - 1; k >= 0; k--) {
if (up[k][u] != up[k][v]) { // 关键:跳了还不相等才跳
u = up[k][u];
v = up[k][v];
}
}
// 3. 此时 u, v 是 LCA 的两个不同子节点
return up[0][u];
}为什么"跳了还不相同才跳"?因为我们要停在刚好低于 LCA 的位置。如果跳了之后相同,说明跳过头了(到了 LCA 或更高),不能跳。
为什么从大到小枚举 k?因为大步长优先。如果从小到大,可能跳过头后就回不来了。
树上距离
int dist(int u, int v) {
int w = lca(u, v);
return depth[u] + depth[v] - 2 * depth[w];
}扩展:带权倍增
不只是祖先,任何"沿路径累计"的信息都能倍增:
// up[k][u] = 第 2^k 个祖先
// mx[k][u] = 从 u 到其 2^k 祖先路径上的最大边权
mx[k][u] = max(mx[k-1][u], mx[k-1][ up[k-1][u] ]);典型题:"树上两点路径的最大边权最小值"。
应用四:其他倍增场景
1. 快速跳指针
链表/数组中,每个位置有
next[i],求从s跳n次后在哪。
// next_[k][i] = 从 i 跳 2^k 次的位置
for (int k = 1; k < LOG; k++)
for (int i = 1; i <= n; i++)
next_[k][i] = next_[k - 1][next_[k - 1][i]];典型:字符串匹配里跳 fail 指针、自动机上跳转移。
2. 求 k 次操作后的状态
一个状态转移,求。
只要 能复合(),就能倍增。
3. 二分 + 倍增:树上二分
从 u 往上走,找到最远的满足条件的祖先。
int u = start;
for (int k = LOG - 1; k >= 0; k--) {
int anc = up[k][u];
if (anc && check(anc)) // 跳 2^k 后仍满足条件
u = anc; // 就跳
}
// u 是最远的满足条件的祖先这就是"二进制贪心"——从大到小试,能跳就跳。和 LCA 的第二步是同一个套路。
4. 后缀数组 / 后缀自动机里的倍增
后缀数组的经典构造算法(倍增法):先按长度为 1 的子串排序,再按长度 2、4、8… 排序, 或。
5. 二进制拆分优化多重背包
有 个相同物品,不是 枚举,而是拆成 的若干组 → 组,每组做一次 01 背包。
for (int k = 1; k <= c; k <<= 1) {
addItem(w * k, v * k);
c -= k;
}
if (c > 0) addItem(w * c, v * c);复杂度总结
| 场景 | 预处理 | 单次查询 | 空间 |
|---|---|---|---|
| 快速幂 | — | ||
| ST 表 | |||
| LCA | |||
| 跳指针 |
LOG 的取值:。 取 17, 取 20。宁可多开 1~2 位。
常见坑
- LOG 开太小:数组越界,或"跳不到根"。建议
LOG = 20起步(覆盖) - LCA 里
up[0][root]没设成自己:up[k][root] = 0,然后up[k-1][0]越界。要么设成 root,要么特判 - ST 表用于求和:重叠部分会重复计算。求和用前缀和或线段树
lg[]数组没初始化:lg[1] = 0必须显式设置- ST 表的数组维度顺序:
st[K][N]还是st[N][K]?建议st[K][N](k 在外层),内存连续访问更好,且N很大时不会爆栈 - 倍增递推顺序错:必须先算完所有
up[k-1][*],才能算up[k][*]。循环顺序是k在外、i在内 - 树上倍增时忘了
depth[0] = -1:会让根的 depth 变成 1 而不是 0,导致距离算错 - 快速幂的溢出:
res * a在mod接近 时超过long long。用__int128 - LCA 第二步写成从小到大枚举:会跳过头,答案错误