倍增算法（Binary‑Lifting / 快速幂）在 C++ 中的完整学习指南

字数：约 5,000 字
目标：把“倍增算法”拆解成概念、实例、代码、复杂度、误区，让你在 C++ 中既能快速写出高效实现，又能在实践中把握细节。

---

1. 什么是“倍增算法”？

在算法与数据结构中，“倍增”通常有两种主要含义：

语境	名称	主要用途	典型实现方式
1	快速幂（Exponentiation by Squaring）	计算 abab 或矩阵幂、组合数等	递归或迭代把幂拆成二进制，平方与幂的拆分
2	二进制提升（Binary Lifting）	树形结构上的祖先查询、最小公共祖先（LCA）	预处理每个节点的 2k2k‑级祖先，二进制搜索

为什么叫「倍增」？
在快速幂中，算子（如乘法）以 2 的幂次扩展：

…
而在二进制提升中，节点向上“跳跃”长度为 2、4、8、…。

接下来我们分别针对这两种常见应用独立展开讲解，以实例代码配合图示，帮助你把“倍增”落到实处。

---

2. 快速幂（Exponentiation by Squaring）

2.1 基本思想

你需要很方便地做某些幂运算，例如：

• 31000003100000 的值（大数）
• 求矩阵 AA 的 100 000 次幂（图论中的转移矩阵）
• 计算组合数 C(n,k)C(n,k) 时用到的“快速取模指数”

核心技巧：把指数 bb 以二进制展开，从最低位开始处理；每处理一位，就把基数平方一次。
这与直接做 repeated multiplication 的 O(b)O(b) 对比，时间复杂度降到 O(log⁡b)O(logb)。

2.2 示例 1：整数指数（无模）

// 直接递归版本（不推荐，栈深可能爆）
long long power(long long a, long long b) {
    if (b == 0) return 1;
    long long half = power(a, b / 2);
    if (b % 2 == 0) return half * half;
    else return half * half * a;
}

2.3 示例 2：模幂（适合大数、取模）

using int64 = long long;
const int MOD = 1e9+7;

// 循环实现
int64 mod_pow(int64 a, int64 b, int mod = MOD) {
    int64 res = 1;
    a %= mod;
    while (b > 0) {
        if (b & 1) res = (res * a) % mod;   // 选bit：乘基
        a = (a * a) % mod;                   // 平方基
        b >>= 1;                              // 右移
    }
    return res;
}

解释：

步骤	操作	说明
1	b & 1	判断当前指数最低位是否为1
2	res = res * a % mod	如果为1，则把对应的幂乘入结果
3	a = a * a % mod	平方基，以便处理下一位
4	b >>= 1	移位，进入下一位

时间复杂度：O(log⁡b)O(logb)。
空间复杂度：O(1)O(1)。

2.4 进阶：矩阵快速幂

矩阵乘法天然满足结合律，因此可以用同样的思想做矩阵的幂运算。下面给出 2×2 矩阵的快速幂实现，常用于斐波那契数列、转移矩阵等。

struct Mat {
    long long a, b, c, d; // [a b; c d]
    Mat(long long a_=1, long long b_=0, long long c_=0, long long d_=1) : a(a_), b(b_), c(c_), d(d_) {}
};

Mat mul(const Mat &x, const Mat &y) {
    return Mat(
        (x.a * y.a + x.b * y.c) % MOD,
        (x.a * y.b + x.b * y.d) % MOD,
        (x.c * y.a + x.d * y.c) % MOD,
        (x.c * y.b + x.d * y.d) % MOD
    );
}

Mat mat_pow(Mat base, long long exp) {
    Mat res; // 单位矩阵
    while (exp) {
        if (exp & 1) res = mul(res, base);
        base = mul(base, base);
        exp >>= 1;
    }
    return res;
}

典型应用：斐波那契数列：
Fn=(1110) n−1⋅(10)Fn​=(11​10​)n−1⋅(10​)

---

3. 二进制提升（Binary Lifting）

3.1 场景

在树（Parent‑Child 关系）上进行“祖先查询”是最常见的场景，尤其是：

• LCA（Lowest Common Ancestor）：求两点最近公共祖先
• k‑th ancestor：查询某点向上 k 步的节点
• 边权累加 / 距离：可以搭配二进制提升做区间求和

3.2 思路概述

1. 预处理：对于每个节点 v，记录：

   up[v][k]=the ancestor of v that is 2k steps above.up[v][k]=the ancestor of v that is 2k steps above.

   up[v][0] 就是父节点（或者自己）。

2. 查询：把 k (或者某个 LCA 候选) 写成二进制，按位“跳跃”，每跳一次就把 k 减少相应的 2 的权。

   举例：要查询 13（1101₂） 步上节点：

   • 先跳 8 步 (up[v][3])，
   • 再跳 4 步 (up[ up[v][3] ][2])，
   • 再跳 1 步 (up[ up[ up[v][3] ][2] ][0])。

3. LCA：先把两点提升到相同深度，再同时往上跳，直到祖先相同。

时间复杂度：

• 预处理：O(Nlog⁡N)O(NlogN)
• 查询：O(log⁡N)O(logN)

3.3 示例 1：构建树 + 预处理

const int MAXN = 200005;
const int LOG   = 20;          // 因为 2^19 > 200k

vector<int> g[MAXN];
int up[MAXN][LOG];
int depth[MAXN];

void dfs(int v, int p){
    up[v][0] = p;             // 第一层祖先
    depth[v] = depth[p] + 1;  // 深度
    
    for(int k = 1; k < LOG; ++k){
        up[v][k] = up[ up[v][k-1] ][k-1];   // 2^k 祖先
    }
    for(int to : g[v]){
        if(to == p) continue;
        dfs(to, v);
    }
}

使用提醒：

• 根点的父节点设为 0（或自身），并且 depth[0] = -1，方便计算深度。
• up[v][k] 对于 k 过大时会回到 0，但不会影响后续查询。

3.4 示例 2：k‑th ancestor

int kth_ancestor(int v, int k){
    for(int i = 0; i < LOG; ++i){
        if(k & (1 << i)){
            v = up[v][i];
            if(v == 0) break;   // 超出根，返回 0
        }
    }
    return v;                  // 0 表示不存在
}

3.5 示例 3：LCA（离线+在线）

在线版（查询时随时得到答案）：

int lca(int u, int v){
    if(depth[u] < depth[v]) swap(u, v);
    // 把 u 提升到 v 的深度
    u = kth_ancestor(u, depth[u] - depth[v]);
    if(u == v) return u;
    for(int i = LOG-1; i >= 0; --i){
        if(up[u][i] != up[v][i]){
            u = up[u][i];
            v = up[v][i];
        }
    }
    return up[u][0];   // 现在 u 和 v 的父亲相同，为 LCA
}

离线版（若查询量非常大，可以用 Tarjan 的并查集）

这儿我们重点讲在线版；离线版在海量查询时 CPU 上的比对更好（仅仅每节点插入一次集合）。

3.6 示例 4：边权累计（加权树）

如果树的边上有权值（或距离），你既要记录祖先，也要累积到该祖先的距离。
预处理时额外维护：

int64 dist[MAXN][LOG];   // dist[v][k] = 距离从 v 到 up[v][k]

void dfs(int v, int p, int64 w){   // w = weight(v, p)
    up[v][0]    = p;
    dist[v][0]  = w;
    depth[v]    = depth[p] + 1;

    for(int k=1;k<LOG;++k){
        up[v][k]   = up[ up[v][k-1] ][k-1];
        dist[v][k] = dist[v][k-1] + dist[ up[v][k-1] ][k-1];
    }
    ...
}

查询到指定 k‑th ancestor 时返回距离：

int64 dist_kth(int v, int k){
    int64 ans=0;
    for(int i=0;i<LOG;++i)
        if(k & (1<<i)){
            ans += dist[v][i];
            v = up[v][i];
        }
    return ans;
}

至此，你能用二进制提升算出任意节点到其 k‑ancestor 的距离。

3.7 细节与陷阱

场景	常见误区	对策
预处理	LOG 取值不足	LOG 取 ceil(log2(N)) + 1 或者 20（大约 1M）
k‑th ancestor 超范围	对 0 节点取下一级	在代码中判断 v==0，直接返回 0
LCA 路径	两个节点互为祖先	在 if(u==v) 前判断即可
边权求和	取模重复求和	做 %MOD 保持在 int 范围内
深度计数	根点深度错误	保证根点 depth[root] = 0，或者 -1 与 +1 的配合

---

4. 代码完整示例：LCA + 距离 + 组合运算

下面给出一个完整可运行的程序示例，包含：

• 树建（根设为 1）
• 二进制提升的预处理
• LCA 查询
• 距离查询（无权）
• 快速幂的辅助函数
• 组合数存取（若需大 n 采用 Lucas‑Theorem + 模）

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200005;
const int LOG   = 20;
const int MOD   = 1e9+7;

vector<int> g[MAXN];
long long up[MAXN][LOG];
int depth[MAXN];

// ---------- 快速幂 ----------
long long mod_pow(long long a, long long b){
    long long res=1;
    a%=MOD;
    while(b){
        if(b&1) res=res*a%MOD;
        a=a*a%MOD;
        b>>=1;
    }
    return res;
}

// ---------- 预处理 ----------
void dfs(int v, int p){
    up[v][0] = p;
    depth[v] = depth[p] + 1;
    for(int i=1;i<LOG;++i)
        up[v][i] = up[ up[v][i-1] ][i-1];
    for(int to : g[v])
        if(to!=p) dfs(to,v);
}

// ---------- k‑ancestor ----------
int kth_ancestor(int v, int k){
    for(int i=0;i<LOG && v;i++){
        if(k&(1<<i)) v=up[v][i];
    }
    return v;                 // 0 表示不存在
}

// ---------- LCA ----------
int lca(int u, int v){
    if(depth[u] < depth[v]) swap(u,v);
    u = kth_ancestor(u, depth[u]-depth[v]);
    if(u==v) return u;
    for(int i=LOG-1;i>=0;--i){
        if(up[u][i]!=up[v][i]){
            u=up[u][i];
            v=up[v][i];
        }
    }
    return up[u][0];
}

// ---------- 距离 ----------
int dist(int u, int v){
    return depth[u]+depth[v]-2*depth[lca(u,v)];
}

// ---------- 组合数 ----------
const int NMAX = 400000;   // 需要大于等于 MAXN
long long fact[NMAX+1], invfact[NMAX+1];
long long mod_inv(long long x){ return mod_pow(x, MOD-2); }

void init_fact(){
    fact[0] = 1;
    for(int i=1;i<=NMAX;++i) fact[i] = fact[i-1]*i%MOD;
    invfact[NMAX] = mod_inv(fact[NMAX]);
    for(int i=NMAX-1;i>=0;--i) invfact[i] = invfact[i+1]*(i+1)%MOD;
}

long long C(int n, int k){
    if(k<0||k>n) return 0;
    return fact[n]*invfact[k]%MOD*invfact[n-k]%MOD;
}

// ---------- 主程序 ----------
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n;
    for(int i=0;i<n-1;++i){
        int u,v; cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    depth[0] = -1;     // 预防 depth[1] = 0
    dfs(1,0);          // 根设 1

    init_fact();       // 预处理组合数

    cin >> m;
    while(m--){
        int type; cin>>type;
        if(type==1){    // LCA
            int u,v; cin>>u>>v;
            cout << lca(u,v) << '\n';
        }else if(type==2){ // k‑ancestor
            int u,k; cin>>u>>k;
            int anc = kth_ancestor(u,k);
            cout << (anc?anc:-1) << '\n';   // -1 代表不存在
        }else if(type==3){ // 距离
            int u,v; cin>>u>>v;
            cout << dist(u,v) << '\n';
        }else if(type==4){ // 快速幂
            long long a,b; cin>>a>>b;
            cout << mod_pow(a,b) << '\n';
        }else if(type==5){ // 组合数
            int n,k; cin>>n>>k;
            cout << C(n,k) << '\n';
        }
    }
    return 0;
}

输入格式（示例）

1. n 给出结点数
2. 接下来的 n-1 行给出树边
3. m 代表查询数
4. 接下来 m 行格式：
   • 1 u v → 求 LCA
   • 2 u k → 求 u 的 k‑th ancestor
   • 3 u v → 距离
   • 4 a b → abmod  MODabmodMOD
   • 5 n k → C(n,k)mod  MODC(n,k)modMOD

---

5. 进阶：树链分块（Heavy‑Light Decomposition） + 二进制提升

二进制提升专用于单个祖先查询（或路径长度）。如果你需要对路径做区间操作（例如最小值、和、最大值），可以结合 Heavy‑Light Decomposition (HLD) 与线段树来实现。

步骤	说明
1	先跑一次树 DP 统计每个节点的子树大小
2	挑选 “heavy” 子树（最大子树）形成链
3	为每条链建立线段树/绳子，节点在链上的顺序为 DFS 排序
4	路径查询时把路径拆分成若干条链，在线段树上做区间查询
5	若需要 k‑th ancestor 也可用二进制提升（因为 HLD 也需要 up[v][i]）

代码量大、实现细节较多，这里不再展开。
如果你接下来会做代码竞赛，建议先掌握 LCA + bisect，再投入 HLD。

---

6. 实战案例：路程与费用计算

问题描述：
给定一棵无权树上的各点之间的行程费用分为两种：

1. 单价：单位距离 1 * 计费权重 (权重可为 0)
2. 优惠：若某条路径上所有边的权重之和超过阈值 T，则费用为 S（固定）。
   需要支持多次查询：给定两个节点 u,v，求他们之间的最小费用。

思路：

• 首先预处理 up 表和 dist（无权距离，边权 1）。
• 对每条边记录其 权重。
• 提前把所有路径（u, v）访问到的边集中记下来，做一次 树上线段树 记录累计权重。
• 用二进制提升实现 k‑th ancestor，沿着路径向上合并累计权重判断是否 > T。
• 如果超过阈值就返回 S，否则返回距离。

这只是一个思路框架，具体实现复杂 200 行以上，按需写入。

---

7. 误区纠正

误区	真相	如何避免
把 LCA 写成二叉搜索	LCA 不是搜索树，而是先把两点归平深再同步跳。	不要用 STL lower_bound 等函数，直接用 kth_ancestor。
预处理时忘记父节点	up[v][0] 必须是父节点，否则后续的 up[v][k] 计算类 0 指针错误。	在 DFS 第一行写 up[v][0] = p;
把 depth[0] 设为 0	当根点的父节点是 0 时，根点的深度会多 1，导致 LCA 逻辑错误。	把 depth[0] = -1 或在 dfs 里只计算从 1 开始。
用 64 位存距离，导致溢出	距离是节点深度差，最大 ≤ N-1，32 位足够。	若是链路权重很大，用 int64_t；若无权，直接用 int。
当 k>depth	kth_ancestor 直接返回 0 或自己，但错误调用后会导致数组越界。	在调用前做 if(k > depth[v]) return 0;

---

8. 性能优化技巧

技巧	说明	适用场景
预置 vector<int> 容量	避免多次扩容	较大节点数（≥10⁵）
用 static int dp[N][LOG] 而不是 vector	内存连续、更快访问	与算法中 up 结构吻合
用 inline 或头文件实现	减少函数调用开销	查询频繁的在线解题
计算 LOG = 20 稳妥	2²⁰ ≈ 1,048,576 > 任意 n <= 10⁶	预防 2^k 超出数值
做 mod_pow 时使用循环而非递归	递归会栈开销	需要多次幂运算

---

9. 让 C++ 代码“自带文档”的写法

/**
 * @file binary_lifting.hpp
 * @brief C++ template for binary lifting (LCA, kth ancestor, distance)
 * All functions are O(log N) after O(N log N) preprocessing.
 *
 * @note
 *   - Root is assumed to be `1` and its parent is set to `0`.
 *   - depth[0] is set to -1 to make depth[1]==0.
 *   - `LOG` should be set according to maximum node number.
 *
 * @example
 *   // Tree input
 *   cin >> n;
 *   for (int i = 0; i < n-1; ++i) {
 *       int u, v; cin >> u >> v;
 *       add_edge(u, v);
 *   }
 *   // Preprocessing
 *   depth[0] = -1;  // prepare for dfs(1, 0);
 *   dfs(1, 0);
 *
 *   // Queries
 *   cout << lca(4, 7) << endl;          // nearest common ancestor
 *   cout << kth_ancestor(8, 3) << endl;  // ancestor 3 levels up
 *   cout << dist(4, 7) << endl;          // distance between nodes
 */

通过这样的注释，你可以轻松把一个“倍增”函数库复制到任意项目，甚至做成 头文件，供多人协作使用。

---

10. 小结

1. 快速幂：把指数拆成二进制；每位对应一次平方与条件乘法；复杂度 O(log⁡b)O(logb)。
2. 二进制提升 LCA：预处理 ancestor 表，查询时逐位跳跃；复杂度 O(Nlog⁡N)O(NlogN)（预处理）+ 实时查询 O(log⁡N)O(logN)。
3. 优势：实现简单、性能稳健；不需要大规模插值或递归深度。
4. 多场景应用：
   • 树结构查询（最近公共祖先、路径长度、区间最值）
   • 矩阵/线性递推快速幂
   • 组合数、斐波那契数列、数论模计算
5. 技巧：
   • 把根设为 1，父节点 0；
   • LOG 取 20 或 ceil(log2(N))+1；
   • dist 处理无权边不需要额外存储；
   • 高速 IO、静态数组避免器型。

练习：

1. 用 C++ 写一个可以求 k‑th 最小值 的链拆分 AN（先写二进制提升再做链拆分）。
2. 给一棵树实现 点更新 + 路径和查询，前面先实现 LCA + 二进制提升。
3. 用 快速幂 计算 C(109,105)mod  109+7C(109,105)mod109+7（利用 Lucas 定理）。

把这些知识机械化写成库后，后续每次竞赛或项目都会受益。祝你编码愉快、算法大咖一路向前！