倍增法CSP-S

💡 核心思想

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

🎯 直觉理解

想象你要从一个楼层跳到另一个楼层。电梯不是一级一级爬，而是有 1层、2层、4层、8层的跳跃按钮。你要跳 13 层，就按 8+4+1 三个按钮。倍增法就是给每个节点预装这些"电梯按钮"，查询时按二进制拆分跳跃。

📝 算法流程

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

⚠️ 常见坑点

📚 相关题目