Binary Lifting

倍增在做什么

**倍增(Binary Lifting)**的核心思想:

预处理出"跳2k2^k 步"的信息,之后任意nn 步都拆成二进制,用O(log⁡n)O(\log n) 次跳跃拼出来。

n=2k1+2k2+⋯+2kmn = 2^{k_1} + 2^{k_2} + \cdots + 2^{k_m}

把O(n)O(n) 次操作压缩成O(log⁡n)O(\log n) 次。

成立的前提:操作满足结合性 / 可合并性——"跳2k+12^{k+1} 步" = "跳2k2^k 步" 再 "跳2k2^k 步"。

跳 13 步 = 跳 8 步 + 跳 4 步 + 跳 1 步
         = 3 次操作(而不是 13 次)

通用形式

定义状态 up[k][x]:从 x 出发,做2k2^k 次操作后到达的位置(或得到的结果)。

递推:

up[k][x]=up[k−1][ up[k−1][x] ]\text{up}[k][x] = \text{up}[k-1]\big[\ \text{up}[k-1][x]\ \big]

up[0][x] = 一次操作的结果(直接算)
up[1][x] = up[0][ up[0][x] ]     ← 两次
up[2][x] = up[1][ up[1][x] ]     ← 四次
...

空间:O(nlog⁡n)O(n \log n)。预处理时间:O(nlog⁡n)O(n \log n)。查询:O(log⁡n)O(\log n)。

应用一:快速幂

最纯粹的倍增(虽然通常不叫这个名字):

an={(a2)n/2n 为偶数a⋅an−1n 为奇数a^n = \begin{cases} (a^2)^{n/2} & n \text{ 为偶数} \\ a \cdot a^{n-1} & n \text{ 为奇数} \end{cases}

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;
}

为什么是O(log⁡n)O(\log n):a 序列是a1,a2,a4,a8,…a^1, a^2, a^4, a^8, \dots,第kk 位是a2ka^{2^k};n 的二进制第kk 位为 1 就乘上对应的项。

注意溢出:mod 接近10910^9 时,res * a 会超 long long(101810^{18})。用 __int128 或先取模再乘。

矩阵快速幂

线性递推式(如斐波那契fn=fn−1+fn−2f_n = f_{n-1} + f_{n-2})可以写成矩阵幂:

(fnfn−1)=(1110)n−1(f1f0)\begin{pmatrix} f_n \\ f_{n-1} \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^{n-1} \begin{pmatrix} f_1 \\ f_0 \end{pmatrix}

配合快速幂,O(log⁡n)O(\log n) 求第nn 项(而不是O(n)O(n) 递推)。

通用化:任何kk 阶线性递推fn=∑cifn−if_n = \sum c_i f_{n-i} 都能写成k×kk \times k 矩阵的幂 →O(k3log⁡n)O(k^3 \log n)。

应用二:ST 表(RMQ)

问题:静态数组,多次查询区间[l,r][l, r] 的最大值,无修改。

思路:st[k][i] = 从ii 开始、长度2k2^k 的区间的最大值。

st[k][i]=max⁡(st[k−1][i], st[k−1][i+2k−1])\text{st}[k][i] = \max\big(\text{st}[k-1][i],\ \text{st}[k-1][i + 2^{k-1}]\big)

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]);
}

查询的原理:用两个长度2k2^k 的区间覆盖[l,r][l, r],允许重叠。

[l                         r]
[  2^k  ]
           [  2^k  ]
        ↑ 重叠不影响 max/min 的正确性

为什么允许重叠:因为max⁡\max 和min⁡\min 是幂等的(重复计算不改变结果)。所以 ST 表只适用于可重复贡献的问题(max、min、gcd、按位与/或),不能用于求和(会重复计算重叠部分)。

问题类型能否用 ST 表
区间 max / min✓
区间 gcd✓
区间按位与 / 或✓
区间和✗(用前缀和)

复杂度:预处理O(nlog⁡n)O(n \log n),查询O(1)O(1),空间O(nlog⁡n)O(n \log n)。

对比线段树:ST 表查询O(1)O(1) 更快,但不支持修改。静态 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] = 节点uu 的第2k2^k 个祖先。

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?因为大步长优先。如果从小到大,可能跳过头后就回不来了。

树上距离

dist(u,v)=depth[u]+depth[v]−2×depth[lca(u,v)]\text{dist}(u, v) = \text{depth}[u] + \text{depth}[v] - 2 \times \text{depth}[\text{lca}(u,v)]

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 次操作后的状态

一个状态转移ff,求fn(x)f^n(x)。

只要ff 能复合(fa+b=fa∘fbf^{a+b} = f^a \circ f^b),就能倍增。

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… 排序,O(nlog⁡2n)O(n \log^2 n) 或O(nlog⁡n)O(n \log n)。

5. 二进制拆分优化多重背包

有cc 个相同物品,不是O(c)O(c) 枚举,而是拆成1,2,4,…,2k,余数1, 2, 4, \dots, 2^k, \text{余数} 的若干组 →O(log⁡c)O(\log c) 组,每组做一次 01 背包。

for (int k = 1; k <= c; k <<= 1) {
    addItem(w * k, v * k);
    c -= k;
}
if (c > 0) addItem(w * c, v * c);

复杂度总结

场景预处理单次查询空间
快速幂—O(log⁡n)O(\log n)O(1)O(1)
ST 表O(nlog⁡n)O(n \log n)O(1)O(1)O(nlog⁡n)O(n \log n)
LCAO(nlog⁡n)O(n \log n)O(log⁡n)O(\log n)O(nlog⁡n)O(n \log n)
跳指针O(nlog⁡n)O(n \log n)O(log⁡n)O(\log n)O(nlog⁡n)O(n \log n)

LOG 的取值:⌈log⁡2n⌉+1\lceil \log_2 n \rceil + 1。n=105n = 10^5 取 17,n=106n = 10^6 取 20。宁可多开 1~2 位。

常见坑

  • LOG 开太小:数组越界,或"跳不到根"。建议 LOG = 20 起步(覆盖10610^6)
  • 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 接近10910^9 时超过 long long。用 __int128
  • LCA 第二步写成从小到大枚举:会跳过头,答案错误