算法专题讲义：倍增算法 (Doubling Algorithm)

作者： 作者的头像   huolong , 时间：2026-08-15 16:16:02 , 所有人可见, 阅读  6

算法专题讲义：倍增算法 (Doubling Algorithm)

倍增算法（Doubling Algorithm）是一种在处理大规模数据和区间查询时非常高效的算法设计思想。它的核心在于“将线性步长转换为指数步长”，即不采用每次加 $1$ 的方式递增，而是每次以 $2$ 的幂次（$1, 2, 4, 8, \dots, 2^j$）进行跳跃。

本讲义将系统介绍倍增算法的概念、原理、二维倍增表的初始化与构建方式，并通过三个经典应用（快速幂、RMQ、LCA）及其对应题目，帮助你深入掌握该算法。

1. 倍增算法的核心概念与原理

1.1 什么是倍增？

在日常算法设计中，我们经常遇到需要从状态 $A$ 转移到状态 $B$ 的场景。如果采用传统的逐步移动（如指针每次向后移动 $1$ 个单位，或者树上每次向上跳一个节点），在最坏情况下时间复杂度为 $O(N)$。

倍增思想的核心在于：任何一个正整数 $D$ 都可以唯一地拆分为若干个不同的 $2$ 的幂次之和（即二进制表示）。例如： $$13 = 8 + 4 + 1 = 2^3 + 2^2 + 2^0$$

如果我们提前预处理出移动 $2^0, 2^1, 2^2, \dots, 2^j$ 步所到达的位置（或区间信息），那么对于任意距离 $D$，我们都可以在 $O(\log D)$ 的步数内凑出该距离。

1.2 为什么是 $2^j$ 步？

  1. 二进制拆分：任意距离都可以在对数级别的时间内被 $2$ 的幂次精确组合出来。
  2. 状态合并（递推关系）：跳跃 $2^j$ 步的效果，等于先跳跃 $2^{j-1}$ 步，再跳跃 $2^{j-1}$ 步。 即： $$\text{Step}(2^j) = \text{Step}(2^{j-1}) + \text{Step}(2^{j-1})$$ 这种性质使得我们可以利用动态规划（DP）的思想，在 $O(N \log N)$ 的时间内完成状态的初始化预处理。

2. 初始化倍增表：二维数组展示

倍增算法的预处理通常使用二维数组来存储。最常见的应用有两类：树上祖先倍增表 和 区间最值倍增表（ST表）。

2.1 树上祖先倍增表 fa[i][j]

在树上应用中，我们定义 fa[i][j] 表示节点 $i$ 向上（朝根节点方向）跳 $2^j$ 步所到达的祖先节点。

递推关系：

$$fa[i][j] = fa[\,fa[i][j-1]\,][j-1]$$ 解释：节点 $i$ 向上跳 $2^j$ 步，等于先跳 $2^{j-1}$ 步到达 $mid = fa[i][j-1]$，再从 $mid$ 向上跳 $2^{j-1}$ 步。

二维数组可视化展示：

假设有一棵树结构如下，其中节点 $4$ 为根节点：

    4 (根)
   / \
  1   2
 / \
3   5

定义超出根节点的祖先为 $0$（代表无效节点）。我们来构建 fa[i][j] 表（$N=5$，最大跳跃步数 $2^2=4$，即 $j \in [0, 2]$）：

节点 $i$ $j = 0$ ($2^0=1$ 步) $j = 1$ ($2^1=2$ 步) $j = 2$ ($2^2=4$ 步)
1 4 0 0
2 4 0 0
3 1 4 0
4 0 0 0
5 1 4 0
  • 计算示例：求 fa[3][1]（节点 $3$ 向上跳 $2$ 步）。 根据递推式：fa[3][1] = fa[ fa[3][0] ][ 0 ] = fa[1][0] = 4。 从表中可以直接查出结果为 $4$。

2.2 区间最值倍增表 dp[i][j] (ST 表)

在区间最值查询（RMQ）中，我们定义 dp[i][j] 表示以 $i$ 为起点，长度为 $2^j$ 的区间内的最值（即区间 $[i, i + 2^j - 1]$ 的最值）。

递推关系（以区间最小值为例）：

$$dp[i][j] = \min(dp[i][j-1], \; dp[i + 2^{j-1}][j-1])$$ 解释：长度为 $2^j$ 的区间可以均分为两半，前半部分起点为 $i$，长度为 $2^{j-1}$；后半部分起点为 $i + 2^{j-1}$，长度为 $2^{j-1}$。

二维数组可视化展示：

假设输入数组为 $A = [3, 2, 4, 5, 6, 8, 1, 2]$ （下标从 $0$ 开始，共 8 个元素）：

索引 $i$ $A[i]$ $j=0$ (长度为 1) $j=1$ (长度为 2) $j=2$ (长度为 4) $j=3$ (长度为 8)
0 3 3 $\min(3,2) = 2$ $\min(2,4) = 2$ $\min(2,1) = 1$
1 2 2 $\min(2,4) = 2$ $\min(2,5) = 2$ $\min(2,2) = 1$
2 4 4 $\min(4,5) = 4$ $\min(4,6) = 4$ 越界
3 5 5 $\min(5,6) = 5$ $\min(5,1) = 1$ 越界
4 6 6 $\min(6,8) = 6$ $\min(6,1) = 1$ 越界
5 8 8 $\min(8,1) = 1$ $\min(1,2) = 1$ 越界
6 1 1 $\min(1,2) = 1$ 越界 越界
7 2 2 越界 越界 越界
  • 计算示例：求 dp[0][2]（区间 $[0, 3]$ 的最小值）。 根据递推式：dp[0][2] = min(dp[0][1], dp[2][1]) = min(2, 4) = 2。

3. 倍增算法的经典应用

应用 1：快速幂 (Binary Exponentiation)

  • 思想：要求 $a^b \bmod p$，我们不可能进行 $b$ 次循环乘法。可以将指数 $b$ 进行二进制拆分，仅计算 $a^{2^0}, a^{2^1}, a^{2^2}, \dots$ 并在 $b$ 的二进制对应位为 $1$ 时乘入结果。时间复杂度降为 $O(\log b)$。

应用 2：RMQ (静态区间最值查询)

  • 思想：使用 ST 表进行预处理后，对于任意查询区间 $[L, R]$，其长度为 $len = R - L + 1$。 令 $k = \lfloor \log_2(len) \rfloor$，则区间 $[L, R]$ 可以完全由两个长度为 $2^k$ 且有重叠的子区间 $[L, L + 2^k - 1]$ 与 $[R - 2^k + 1, R]$ 覆盖。 由于最值操作（如 $\min, \max$）具有幂等性（即重叠部分不影响最值结果），我们可以直接 $O(1)$ 得到结果： $$\text{Ans} = \min(dp[L][k], \; dp[R - 2^k + 1][k])$$
  • 注意：ST 表仅适用于静态区间查询。若区间存在修改操作（如“区间加”），则不适合使用 ST 表，需使用线段树等数据结构。

应用 3：LCA (树上最近公共祖先)

  • 思想：求节点 $u$ 和 $v$ 的最近公共祖先。
    1. 对齐深度：不妨设 $depth[u] \ge depth[v]$。利用倍增表 fa[u][j] 将 $u$ 向上提升，直到 $depth[u] == depth[v]$。
    2. 若已重合：说明 LCA 就是当前的 $v$，直接返回。
    3. 同时向上跳：若不重合，利用倍增思想，从大到小尝试让 $u$ 和 $v$ 同时向上跳 $2^j$ 步。为了避免跳过头，只有当 fa[u][j] != fa[v][j] 时才执行跳跃。
    4. 最终答案：循环结束后， $u$ 和 $v$ 将恰好处于 LCA 的下一层，因此答案即为 fa[u][0]。

4. 例题精讲与代码实现

题 1. 157. 快速幂

题目描述

求 $a^b \bmod p$，其中 $p=10^9+7$。 * 数据范围：$a, b \in [1, 10^9]$。

解题思路

直接应用快速幂模板。利用位运算 b & 1 判断当前二进制位是否为 $1$，如果是则累乘到答案中；同时每次循环将底数自乘 a = (a * a) % p，并将指数右移 b >>= 1。

C++ 代码实现

#include <iostream>

using namespace std;

// 快速幂函数，计算 (a^b) % p
long long power(long long a, long long b, long long p) {
    long long res = 1;
    a %= p; // 保证底数在模数范围内
    while (b > 0) {
        if (b & 1) { // 如果当前二进制位为 1
            res = (res * a) % p;
        }
        a = (a * a) % p; // 底数倍增
        b >>= 1;         // 指数右移
    }
    return res;
}

int main() {
    // 提高输入输出效率
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    long long a, b;
    if (cin >> a >> b) {
        long long p = 1000000007;
        cout << power(a, b, p) << "\n";
    }
    return 0;
}

题 2. 4903. RMQ and RAQ

题目描述

给定一个长度为 $n$ 的整数序列 $A$，初始时所有元素均为 $0$。需要处理以下两种操作： 1. 区间加：0 s t x，将区间 $[s, t]$ 内的所有元素都加上 $x$。 2. 区间最小值查询：1 s t，输出区间 $[s, t]$ 内的最小值。 * 数据范围：$1 \le n, q \le 100000$，数组下标 $0$-indexed。

解题思路

由于此题含有 区间加 (RAQ) 操作，如果使用静态的倍增 ST 表，每次更新都需要 $O(n \log n)$ 的时间重构，会面临超时问题。 因此，处理本题需要使用带有懒标记（Lazy Tag）的线段树。线段树在处理区间修改和区间查询时，单次操作复杂度均为 $O(\log n)$。

C++ 代码实现

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXN = 100005;
const long long INF = 2e18; // 使用足够大的数代表正无穷

long long tree[4 * MAXN];
long long lazy[4 * MAXN];

// 下传懒标记
void push_down(int node) {
    if (lazy[node] != 0) {
        tree[2 * node] += lazy[node];
        lazy[2 * node] += lazy[node];
        tree[2 * node + 1] += lazy[node];
        lazy[2 * node + 1] += lazy[node];
        lazy[node] = 0;
    }
}

// 区间加值操作
void update(int node, int start, int end, int l, int r, long long val) {
    if (l <= start && end <= r) {
        tree[node] += val;
        lazy[node] += val;
        return;
    }
    push_down(node);
    int mid = start + (end - start) / 2;
    if (l <= mid) {
        update(2 * node, start, mid, l, r, val);
    }
    if (r > mid) {
        update(2 * node + 1, mid + 1, end, l, r, val);
    }
    tree[node] = min(tree[2 * node], tree[2 * node + 1]);
}

// 区间最小值查询
long long query(int node, int start, int end, int l, int r) {
    if (l <= start && end <= r) {
        return tree[node];
    }
    push_down(node);
    int mid = start + (end - start) / 2;
    long long ans = INF;
    if (l <= mid) {
        ans = min(ans, query(2 * node, start, mid, l, r));
    }
    if (r > mid) {
        ans = min(ans, query(2 * node + 1, mid + 1, end, l, r));
    }
    return ans;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, q;
    if (cin >> n >> q) {
        // 初始时数组元素全为 0，全局变量 tree 已经自动初始化为 0，无需 build
        while (q--) {
            int type;
            cin >> type;
            if (type == 0) {
                int s, t;
                long long x;
                cin >> s >> t >> x;
                update(1, 0, n - 1, s, t, x);
            } else {
                int s, t;
                cin >> s >> t;
                cout << query(1, 0, n - 1, s, t) << "\n";
            }
        }
    }
    return 0;
}

题 3. 5264. 树上倍增解决 LCA 问题

题目描述

求多叉树中指定两个节点的最近公共祖先。 * 输入： * 第一行三个正整数 $N, M, S$，分别表示节点数、询问数和根节点。 * 接下来 $N-1$ 行，表示树上的边。 * 接下来 $M$ 行，表示询问。 * 数据范围：$1 \le N, M \le 5 \times 10^5$。

解题思路

  1. 建树：使用邻接表存储树的边。
  2. 预处理：从根节点 $S$ 开始进行一次 DFS（或 BFS），计算每个节点的深度 depth[i]，并初始化倍增表 fa[i][j]。
  3. 查询：按照“对齐深度”和“倍增同步向上跳”的步骤查找 LCA。

C++ 代码实现

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXN = 500005;
const int MAXLOG = 21; // 2^20 约等于 10^6，足以应对 N=500000 的深度

vector<int> adj[MAXN];
int fa[MAXN][MAXLOG];
int depth[MAXN];

// DFS 预处理深度与倍增表
void dfs(int u, int p) {
    depth[u] = depth[p] + 1;
    fa[u][0] = p;

    // 动态规划填表：2^j 步的祖先等于 2^(j-1) 步祖先的 2^(j-1) 步祖先
    for (int j = 1; j < MAXLOG; ++j) {
        fa[u][j] = fa[fa[u][j - 1]][j - 1];
    }

    for (int v : adj[u]) {
        if (v != p) {
            dfs(v, u);
        }
    }
}

// 树上倍增查询 LCA
int lca(int u, int v) {
    if (depth[u] < depth[v]) {
        swap(u, v); // 保证 u 的深度不小于 v
    }

    // 1. 将 u 向上提升到与 v 相同的深度
    for (int j = MAXLOG - 1; j >= 0; --j) {
        if (depth[fa[u][j]] >= depth[v]) {
            u = fa[u][j];
        }
    }

    // 如果对齐深度后两节点重合，说明 v 就是最近公共祖先
    if (u == v) return u;

    // 2. 双指针同步倍增向上跳
    for (int j = MAXLOG - 1; j >= 0; --j) {
        if (fa[u][j] != fa[v][j]) { // 只有两者的祖先不同时才跳，防止跳过头
            u = fa[u][j];
            v = fa[v][j];
        }
    }

    // 循环结束时，u 和 v 恰好在 LCA 的下一层，它们的父节点即为所求
    return fa[u][0];
}

int main() {
    // 极高数量级的输入输出，必须使用快速读写
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m, s;
    if (cin >> n >> m >> s) {
        for (int i = 0; i < n - 1; ++i) {
            int u, v;
            cin >> u >> v;
            adj[u].push_back(v);
            adj[v].push_back(u);
        }

        // 规定根节点的父节点为 0 节点，depth[0] 默认为 0
        dfs(s, 0);

        for (int i = 0; i < m; ++i) {
            int u, v;
            cin >> u >> v;
            cout << lca(u, v) << "\n";
        }
    }
    return 0;
}

【例题 4】3133. 天才的记忆 (标准静态 RMQ)

题目分析

本题是一道标准静态 RMQ 题： 1. 数据无修改：初始输入序列后，全为查询操作。 2. 查询次数大：适合采用 ST 表。 3. 时间限制：预处理 $O(N \log N)$，单次查询 $O(1)$。配合快速读入，可以轻松通过。

计算步骤

  • 初始化：设 f[i][j] 表示从第 $i$ 个数开始，长度为 $2^j$ 的区间内的最大值。
    • 边界状态：f[i][0] = A[i]
    • 递推计算：f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1])
  • 预处理对数数组：为了实现 $O(1)$ 的查询，避免重复调用 log() 函数，我们可以在 $O(N)$ 时间内预处理出 $\lfloor \log_2 x \rfloor$ 的值，存入 lg[x] 数组中。
  • 查询： 对于询问区间 $[A, B]$，设区间长度 $len = B - A + 1$。 令 $k = \lg[len]$。 区间最大值为：max(f[A][k], f[B - (1 << k) + 1][k])。

C++ 代码实现

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXN = 200005; // 根据 100% 数据范围 N <= 200000 设定
const int MAXLOG = 20;

int f[MAXN][MAXLOG];
int lg[MAXN];

int main() {
    // 提高输入输出效率
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    if (cin >> n) {
        // 读入数字序列
        for (int i = 1; i <= n; ++i) {
            cin >> f[i][0];
        }

        // 1. 预处理 log2 数组
        lg[1] = 0;
        for (int i = 2; i <= n; ++i) {
            lg[i] = lg[i / 2] + 1;
        }

        // 2. 预处理 ST 表 (外层枚举指数 j，内层枚举起点 i)
        for (int j = 1; j < MAXLOG; ++j) {
            for (int i = 1; i + (1 << j) - 1 <= n; ++i) {
                f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
            }
        }

        int m;
        if (cin >> m) {
            while (m--) {
                int a, b;
                cin >> a >> b;

                // 3. O(1) 查询区间最大值
                int len = b - a + 1;
                int k = lg[len];
                cout << max(f[a][k], f[b - (1 << k) + 1][k]) << "\n";
            }
        }
    }
    return 0;
}

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com