倍增法CSP-J

💡 核心思想

倍增法是一种通过预处理 2^k 级信息来加速查询的技巧。核心思想是"任何整数都可以表示为二进制形式"，因此任何跳跃都可以分解为若干次 2^k 的跳跃。最典型的应用是：LCA 的倍增预处理、RMQ 的 ST 表、快速幂的推广。

🎯 直觉理解

倍增法就是"一步跨 2 的幂"：与其一格一格走 100 步，不如先跨 64 步、再 32 步、再 4 步。只跳 $O(log n)$ 次就能到达任何位置。

最经典的应用是快速幂（$a^b$ 把 $b$ 拆成二进制）和 LCA（求树上两点最近公共祖先，先预处理每个点向上 $2^k$ 步的祖先）。

核心是预处理表 $up[u][k]$ 表示从 u 向上跳 $2^k$ 步。倍增法的共同套路：先花 $O(n log n)$ 预处理，再对每个询问 $O(log n)$ 回答。

📝 算法流程

1. 确定最大幂次 LOG = floor(log2(n)) + 1
2. 预处理 f[i][0] = i 的直接父节点/后继
3. 递推：f[i][k] = f[f[i][k-1]][k-1]（i 的 2^k 级祖先）
4. 查询时：将跳跃距离拆分为二进制，从高到低逐位跳跃

$$f[i][k] = f[f[i][k-1]][k-1]$$

$$\text{查询：}x \text{ 跳 }d \text{ 步} = \sum_{k=0}^{LOG} (d \gg k \& 1) ? f[x][k] : x$$

📊 复杂度分析

💻 参考实现（C++）

#include 
using namespace std;

// 倍增法：从 1 跳到 n 的最少步数（每次可以跳 2^k 步）
const int LOG = 20;
int f[100005][LOG]; // f[i][k]：从 i 跳 2^k 步到达的位置

void init(int n) {
    // 假设规则：从 i 可以直接跳到 i+1
    for (int i = 1; i <= n; i++) f[i][0] = i + 1;
    for (int k = 1; k < LOG; k++)
        for (int i = 1; i <= n; i++)
            f[i][k] = f[f[i][k-1]][k-1];
}

int jump(int x, int d) {
    for (int k = 0; k < LOG; k++)
        if (d >> k & 1) x = f[x][k];
    return x;
}

int main() {
    init(100);
    cout << jump(1, 13) << endl; // 1 + 13 = 14
    return 0;
}

⚠️ 常见坑点

📚 相关题目