---
title: "倍增法"
description: "枚举、模拟、贪心、递归、二分、动态规划、图论等经典算法。"
---

> Documentation Index
> Fetch the complete documentation index at: https://cppguide.xyz/llms.txt
> Use this file to discover all available pages before exploring further.

# 倍增法

![](https://img.dailyup.xyz/originals/8208463062096-a69f4e19-2abf-4ef3-bef7-af0e0aa1fcc3.png)

### 倍增法（Binary Lifting）概述

**倍增法**（Binary Lifting）是一种高效的算法思想，主要用于**跳跃式查询**和**倍增查询**等问题。在解决问题时，倍增法可以将时间复杂度从线性 O(n) 减少到对数 O(log n)。

倍增法的核心思想是：

1. 通过预处理阶段，存储跳跃的“倍数”关系（比如：2倍、4倍、8倍等）。
2. 在查询阶段，利用这些预处理数据快速定位答案。


### 主要应用场景

1. **树上最近公共祖先（LCA）查询**
    - 利用倍增法快速求解两个节点的最近公共祖先。
2. **跳跃查询问题**
    - 比如：在链表或数组中，从某个位置开始，经过 k 步后会到达哪个位置。
3. **区间快速查询**
    - 例如：求某个值的倍数位置。


### 基本原理：利用二进制表示加速跳跃

给定一个查询问题，比如 “从某个点 u，经过 k 步到达哪个点？”  
我们可以利用二进制的特性，将 k 分解成若干个 2ⁱ 的和。

例如：

- k=13，二进制表示为 1101。
    - k = 8 + 4 + 1 = 2³ + 2² + 2⁰

**思想：**  
我们只需要预处理出 “从某个点出发，跳跃 2ⁱ 步后的点”，然后在查询时，利用 k 的二进制表示组合这些 2ⁱ 步即可。


### 应用一：跳跃查询问题

#### 问题描述

在一个数组或链表中，每个点指向一个下一位置。给定一个起点 u，我们想知道从 u 出发，经过 k 步会到达哪个位置？

---

#### **解题步骤**

1. **预处理阶段：倍增表的构建**
    
    - 设 `f[i][j]` 表示从节点 i 出发，经过 2ʲ 步后到达的节点。
    - 状态转移方程： f[i][j] = f[f[i][j-1]][j-1] 即：从节点 i 出发，走 2ʲ 步，可以拆分为走两次 2^(j-1) 步。
2. **查询阶段：分解 k**
    
    - 将 k 表示为二进制的若干个 2ⁱ 之和。
    - 对于 k 的每一位 1，累加对应的 2ⁱ 步数。


#### 代码实现

假设有 n 个点，每个点有一个 `next` 指向它的下一位置。

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

const int MAXN = 100010;
const int LOG = 20;

int f[MAXN][LOG];

void preprocess(int n, vector<int>& next) {
    for (int i = 1; i <= n; i++) {
        f[i][0] = next[i];
    }

    for (int j = 1; j < LOG; j++) {
        for (int i = 1; i <= n; i++) {
            f[i][j] = f[f[i][j-1]][j-1];
        }
    }
}

int query(int u, int k) {
    for (int j = 0; k > 0; j++) {
        if (k & 1) {
            u = f[u][j];
        }
        k >>= 1;
    }
    return u;
}

int main() {
    int n = 5;
    vector<int> next = {0, 2, 3, 4, 5, 5};

    preprocess(n, next);

    int start = 1, steps = 7;
    cout << "从节点 " << start << " 经过 " << steps << " 步到达节点：" << query(start, steps) << endl;

    return 0;
}
```


#### **代码解释**

1. **预处理倍增表：**
    
    - `f[i][0]` 表示从 i 出发，走1步到达的位置。
    - `f[i][j]` 根据状态转移方程构建。
2. **查询：**
    
    - 将 k 的二进制表示逐位检查。
    - 如果 k 的某一位为 1，就执行对应的 2ⁱ 步跳跃。
3. **复杂度分析：**
    
    - **预处理时间复杂度：** O(n log n)
    - **单次查询时间复杂度：** O(log k)


### 应用二：树上 LCA 问题

倍增法也可以用来求解**树上两个节点的最近公共祖先（LCA）**。方法类似，预处理每个节点的 2ⁱ 级父节点，然后快速跳跃到目标层次找到公共祖先。

---

### 总结

1. **倍增法的核心思想：**  
    利用二进制分解，将查询问题转换为若干次 2ⁱ 跳跃的组合。
    
2. **主要步骤：**
    
    - 预处理阶段：构建倍增表。
    - 查询阶段：利用倍增表加速跳跃。
3. **时间复杂度：**
    
    - **预处理：** O(n log n)
    - **单次查询：** O(log n)

倍增法是一种非常高效的算法技巧，在树结构、跳跃查询等场景中有广泛应用。

## 小结

Source: https://cppguide.xyz/algorithm/binarylifting/index.mdx