CC++ & Algorithm

跳台阶的智慧：倍增法思想

困难8
语言版本：C++Python
概述：用“每次跳2^k步”的比喻讲解倍增法，告诉你为什么用指数级跳跃可以快速解决问题。

跳台阶的智慧：倍增法入门

你有没有遇到过这种情况：从学校门口走到教室，明明只有几百米，但偏偏要绕路，感觉走了好久？或者你有一大堆积木，想从第1块开始，每次跳过固定数量的积木，最后想知道在哪一块。如果只能一步一步走，那真是又慢又累。但如果你有一双“魔法鞋子”，第一次跳1步，第二次跳2步，第三次跳4步，第四次跳8步…… 每次跳的步数都翻倍，那么你很快就能跳到目的地。

这就是倍增法的思想——用指数级跳跃代替线性移动，把需要走很多步的问题，变成只需要跳很少几次。在编程中，倍增法常用来解决“从起点出发，执行大量相同移动”的问题，比如在数组上快速跳转、查找最近公共祖先（LCA）、或者求快速幂等。它的核心就是提前计算好“跳2^k步”的结果，然后通过二进制拆分组合这些跳跃，让原本需要O(n)次的操作变成O(log n)次。

一、什么是倍增法？——用“魔法鞋子”的比喻理解

假设你站在一栋大楼的1楼，想要去101楼。如果只能一次上一级台阶，那需要走100步。但如果有一双魔法鞋子：第一次跨1级，第二次跨2级，第三次跨4级，第四次跨8级……每次都能跨“2的整数次幂”级，那么你只需要7步就能到达（1+2+4+8+16+32+64=127，已经超过101）。这就是倍增法的核心思想：用指数增长的方式快速覆盖距离，而不是一步一步走。

这个比喻里，“每次跳的步数是2的幂”对应着计算机里“二进制拆分的跳跃”。我们不需要真的穿魔法鞋，而是提前准备好一张“跳跃表”：记录从每个位置出发，跳1步、跳2步、跳4步……分别会到达哪里。然后需要跳多少步，就把步数拆成二进制的形式，比如100 = 64+32+4，然后分别跳64步、32步、4步，总共3次跳跃就完成了。

二、倍增法的两个关键步骤

倍增法一般分为两步：预处理 和 查询。就像你提前背好乘法口诀表，然后做题时直接查表，而不是每次重新算。

1. 预处理：建一张“跳跃表”

我们需要一个二维数组 up[i][k]，表示从位置 i 出发，连续跳2^k步之后到达的位置。这个表怎么建呢？

  • 首先，我们得知道“跳1步”（k=0）的去向：up[i][0] = 下一个位置。比如在环形数组里，up[i][0] = (i + 1) % n。
  • 然后，利用递推关系：跳2^k步 = 先跳2^(k-1)步，再跳2^(k-1)步。写成公式： 
    up[i][k] = up[ up[i][k-1] ][k-1]
    意思是：从i出发先跳2^(k-1)步，到达up[i][k-1]，再从那里再跳2^(k-1)步，就相当于总共跳了2^(k-1)+2^(k-1)=2^k步。

生活中的类比：你想知道从家出发，跳8步能到哪，可以先跳4步到一个地方，然后从那里再跳4步。你只需要知道“从任何位置跳4步能到哪”，就能算出跳8步的结果。

2. 查询：用二进制拆分快速跳

当你想要从起点s跳step步时，不必真的跳step次，而是把step写成二进制形式。比如step=13，二进制是1101，即8+4+1。那么：

  • 先检查最低位（第0位）：如果是1，就跳2^0=1步，即 s = up[s][0]
  • 然后step右移一位，检查第1位：如果是0，不跳
  • 继续右移，检查第2位：如果是1，就跳2^2=4步，即 s = up[s][2]
  • 继续右移，检查第3位：如果是1，就跳2^3=8步，即 s = up[s][3]

这样，最多只跳了二进制位数（log2(step)）次，而不是step次。

三、生活中的倍增法例子

例子1：零花钱买零食

小明每周零花钱是10元，他打算用零花钱买1元的棒棒糖。如果他每次只买1根，买100次要100周。但如果他第一次买1根、第二次买2根、第三次买4根……每次翻倍，那么买127根只需要7次。虽然最后可能会多买，但这个方法能让他在短时间内“大采购”。

例子2：考试跳题

考试时，如果你知道每个题目后面连续几题的答案都在同一页，你可以直接翻页。比如从第1题开始，向前跳1题、2题、4题……这样很快就能定位到指定题号。

例子3：排队找同学

学校做操时，同学们站成一排。你想从第1个同学开始，找到他后面第100个同学。如果一个个数要数100次，但如果你提前知道“从任意同学往后跳2、4、8……个位置会到谁”，那么只需要把100拆成64+32+4，跳3次就能找到。

四、C++代码实现：环形数组快速跳步

下面是一个完整的C++程序，展示倍增法的预处理和查询。我们将数组视为环形（最后一个位置的下一个位置是0），这样跳任意步数最终位置都是 (起始 + 步数) % 总位置数，但倍乘法可以跳过中间计算，直接得到结果。

#include <iostream>
#include <cmath>
using namespace std;

const int MAXN = 1000;   // 最大位置数，从0开始编号
int n;                    // 位置总数（例如0到n-1）
int up[MAXN][20];         // up[i][k] 表示从位置i跳2^k步到达的位置

// 预处理：计算所有位置跳2^k步的去向
void init() {
    // 先假设数组是环形的，即最后一个位置的下一个位置是0（模拟循环）
    for (int i = 0; i < n; ++i) {
        up[i][0] = (i + 1) % n;   // 跳1步（2^0=1）
    }
    // k从1开始，直到 2^k 超过n（因为跳n步就会回到原地，再大无意义）
    for (int k = 1; (1 << k) <= n; ++k) {   // 1<<k 就是 2^k
        for (int i = 0; i < n; ++i) {
            // 从i跳2^k步：先跳2^(k-1)步到 up[i][k-1]，再从那里跳2^(k-1)步
            up[i][k] = up[ up[i][k-1] ][k-1];
        }
    }
}

// 从位置s开始，跳step步，返回最终位置
int jump(int s, int step) {
    // 从低位到高位检查step的二进制
    for (int k = 0; step > 0; ++k) {
        if (step & 1) {      // 如果step的二进制这一位是1，就跳2^k步
            s = up[s][k];
        }
        step >>= 1;          // 右移一位，处理下一位
    }
    return s;
}

int main() {
    n = 10;                  // 假设有10个位置0~9，围成一个圈
    init();                  // 预处理出所有跳跃表

    // 测试：从位置0跳100步
    int start = 0;
    int steps = 100;
    int result = jump(start, steps);
    cout << "从" << start << "跳" << steps << "步到达：" << result << endl;
    // 真实计算结果应该是 (0+100) % 10 = 0，但这里直接通过跳跃表快速得到

    // 再测试一个：从位置3跳25步
    start = 3;
    steps = 25;
    result = jump(start, steps);
    cout << "从" << start << "跳" << steps << "步到达：" << result << endl;  // 应该得到(3+25)%10=8

    return 0;
}

代码解释：

  • 数组 up 有20列，因为2^20≈100万，对于本题n=10足够。实际要根据n的最大值确定列数，一般取 log2(MAXN) + 1。
  • 初始化时，第一列 up[i][0] 必须先定义好（跳1步的去向）。
  • 递推公式 up[i][k] = up[ up[i][k-1] ][k-1] 要确保 up[i][k-1] 已经计算好，所以我们按k从小到大循环。
  • 查询时，step & 1 检查当前最低位是否为1，如果是则跳对应的2^k步，然后 step >>= 1 丢弃最低位。每次循环k增加1。

五、常见错误与注意事项

  1. 忘记初始化第一列
    很多新手直接跳过 up[i][0] 的定义，导致后面递推出错。up[i][0] 必须单独设置（比如跳1步到下一个位置），不能从递推得到。

  2. 递推时数组越界
    例：如果位置总数是n，那么 up[i][k-1] 可能超出n-1？不会，因为 up 的索引始终是0到n-1之间的数（因为我们一开始就规定了跳1步只能在0~n-1之间移动）。但注意，如果数组不是环形而是有边界，就要特别处理边界情况（比如跳到最后只能停在原位）。

  3. 预处理列数不够
    如果n很大（比如10^5），那么2^k需要k达到17以上（2^17=131072）。如果数组只开了 [MAXN][15]，则当k太大时越界。一般取 log2(MAXN) + 2 作为列数。

  4. 查询时二进制拆分的边界
    jump 函数中的 for (int k = 0; step > 0; ++k) 是安全的，因为每次循环 step 右移，最终会变成0。但注意：如果 step 很大，而 up 的列数不够（比如只计算到 k=10，但 step 的二进制有11位），那么读取 up[s][10] 再往后就会越界。所以预处理时一定要保证 2^k 至少能覆盖 step 的最大可能值。

  5. 混淆“跳2^k步”和“跳k次”
    倍增法里每一步跳的是2^k步（指数增长），而不是每次跳k步。初学者容易误解为“跳1步、跳2步、跳3步……”，但那是另一种方法。

六、倍增法的更多应用

你可能会想：这个方法除了让题目变得“酷炫”，还有什么实际用途？其实，倍增法在计算机科学中无处不在：

  • 快速幂：计算a^b，可以把b拆成二进制，每次取a的平方，这与跳跃表的思路完全一致。
  • RMQ（区间最值查询）：用ST表预处理任意区间的最值，也是利用倍增思想，从长度1、2、4……逐步扩展。
  • 最近公共祖先（LCA）：在树上找两个节点的最近公共祖先，需要从两个节点同时向上“跳”，利用倍增可以O(log n)完成。
  • 数组上的批量移动：比如你有一个游戏地图，每次移动都走固定步数，可以用倍增法快速计算移动多次后的位置。

如果你已经理解了环形数组上的跳跃，接下来可以尝试自己实现“非环形”的版本（即数组有尽头，跳到最后就停在那里），或者实现树上倍增查找祖先。另外，二分法和倍增法有时容易混淆——二分法是每次将搜索范围减半，而倍增法是每次将步数加倍，两者方向不同，但都利用了指数级别的变化。

七、总结与延伸

倍增法的精髓就是预处理 + 二进制拆分。它把需要O(n)次重复操作的问题，变成了O(log n)次跳跃。就像你玩游戏时获得了一个“加速道具”，让你不再一步一个脚印地走。

现在你可以尝试拓展：

  1. 修改代码，让数组变成线性的（不是环形），即跳到最后一个位置时不再循环，而停留在原地。
  2. 实现一个函数，从位置s跳step步，但每跳一步的规则不同（比如每次跳的步数由另一个数组决定），看是否能继续用倍增法优化。
  3. 学习ST表（Sparse Table），它就是用倍增法解决区间查询的经典结构。

如果未来遇到“需要多次移动”的题目，不妨想一想：能不能用倍增法把步数压缩成对数？这可能就是你解题的关键。

例题精讲

1单选题

使用倍增法思想，从0级台阶出发，每次可以跳2^k步（k为非负整数，且每次可以选择不同的k），要恰好跳到第15级台阶，最少需要跳多少次？

A2次
B3次
C4次
D5次
2判断题

利用倍增法思想求解整数快速幂（计算a^n）时，算法的时间复杂度是O(log n)。

3填空题
以下代码利用倍增法实现快速幂，请在横线处填写正确表达式。
int fastPow(int a, int n) {
    int ans = 1;
    while (n > 0) {
        if (___)   // 判断当前最低位是否为1
            ans *= a;
        a *= a;
        n >>= 1;
    }
    return ans;
}
4单选题

关于倍增法思想，以下哪个说法是错误的？

A倍增法利用指数级增长来减少重复操作的次数。
B倍增法可以用于解决最近公共祖先（LCA）问题。
C倍增法只能用于正整数的幂运算，不能用于其他场景。
D倍增法适用于需要多次查询或跳跃，且数据规模较大的情况。
5填空题
以下代码利用倍增法思想，计算从0级台阶跳到n级台阶所需的最少跳跃次数（每次可以跳2^k步，k任意）。请在横线处填写正确表达式。
int minJumps(int n) {
    int cnt = 0;
    while (n > 0) {
        cnt += ___;
        n >>= 1;
    }
    return cnt;
}