🚀 倍增法
一只小青蛙一次跳 1 格太慢，要是每步都能翻倍：1、2、4、8……很快就能跳出老远！倍增法就是「走 1 步、2 步、4 步、8 步……」地跳，用二进制的秘密把「一步步走很多次」变成「翻倍跳几次」，把时间从 O(n) 缩到 O(log n)。
考纲知识点：倍增的概念
📖
考纲 · 知识点详述
摘自《CCF编程能力等级认证 C++&Python 认证标准》C++ 八级
- (4)掌握倍增法概念。了解倍增法的时间复杂度。
📚
先学一学
花 6 分钟读完下面 5 课，再去闯关就不慌啦
1
🐸 一次比一次翻倍跳
倍增（倍着增）就是每一步都翻倍：1、2、4、8、16……从 1 开始，每跳一次步子就 ×2。要走很远时，不用一步一步数，而是「先跳 1，再跳 2，再跳 4……」。翻倍跳的次数特别少：从 1 翻倍到超过 1000，只需要跳 10 次（1→2→4→8→16→32→64→128→256→512→1024）。
⚡ 快多少？
一步步走 n 步要做 n 次；翻倍跳只要约 log₂n 次。n = 1,000,000 时，一步步要 100 万次，翻倍跳只要 20 次！这就是倍增法的威力。
💡 口诀：倍增就是翻倍走，次数少到 log n；一步两步变四步，大步流星到终点。
2
💡 用 1、2、4、8…能凑出任意步数
🧮 13 = 8 + 4 + 1
任意正整数都能拆成「1、2、4、8、16…」里的一些数相加，就像二进制：13 = 1101₂ = 8+4+1。所以只要提前准备好 1、2、4、8…这些「跳板」，任何距离都能用很少的几块跳板跳到。
💡 口诀：步数拆成二进制，1、2、4、8 随便配；几块跳板就够用，跳得又准又省力。
3
🗺️ 倍增的用武之地
1️⃣ 跳表 / 倍增找位置
在未知长度的有序数组里找目标范围：先跳 1、2、4、8……翻倍逼近，再回头微调，比一次次走快得多。
2️⃣ 区间最值（RMQ）
提前存好「从每个位置开始往后 2^k 个里的最大/最小」，查询任意区间时用两块大区间拼起来，预处理 O(n log n)、查询 O(1)。
3️⃣ 找祖先 / 爬树
在树上从某点往上跳 2^k 步的「祖先表」也提前存好，找最近公共祖先（LCA）时一次跳一大段。
4️⃣ 快速幂
算 a 的 e 次方：把指数 e 按二进制拆开，底数不断自乘翻倍（a、a²、a⁴、a⁸…），只要乘 O(log e) 次而不是 e 次。
💡 口诀：倍增四兄弟：跳表、RMQ、爬树找祖先、快速幂；全是二进制拆步数。
4
💻 读代码：快速幂长什么样
⚙️ fastPow 快速幂
看得懂就好，不用背。要点：指数 e 的二进制哪一位是 1，就把对应的翻倍结果乘进去：
long long fastPow(long long b, long long e, long long mod) {
long long result = 1;
while (e > 0) {
if (e & 1) result = result * b % mod; // 这一位是 1 → 乘进去
b = b * b % mod; // 底数翻倍：b→b²→b⁴→b⁸…
e >>= 1; // 指数右移看下一位
}
return result;
}
long long result = 1;
while (e > 0) {
if (e & 1) result = result * b % mod; // 这一位是 1 → 乘进去
b = b * b % mod; // 底数翻倍：b→b²→b⁴→b⁸…
e >>= 1; // 指数右移看下一位
}
return result;
}
while 每轮把 e 往右移一位，总共只跑 e 的二进制位数次 → O(log e)。要是老老实实乘 e 次就是 O(e)。
💡 口诀：指数看二进制，底数不停自乘；有位就乘进去，跑 O(log e) 次。
5
📏 倍增的时间复杂度 + 行业实际
⏱️ 复杂度口诀
倍增法常常把「走 n 次」变成「走 log n 段」。预处理常常 O(n log n)，之后单次操作只要 O(log n) 甚至 O(1)。判断是不是倍增：看它是不是用 1、2、4、8…翻倍步长。
💡 口诀：看到翻倍步长，想到 log n；预处理换快速查询，值得！
🌟 行业实际
搜索引擎倒排索引跳表、区块链算哈希幂、密码学 RSA 加密里算超大数的幂、游戏里判断角色连续跳跃落点——凡是「算很多次乘方 / 跳很远」的地方，都能见到倍增思想的影子。
🎯
闯关小锦囊 · 考点提醒
- 倍增 = 步长翻倍：1、2、4、8…，把 O(n) 变成 O(log n)。
- 任意整数都能用 1、2、4、8…（二进制）凑出来，比如 13 = 8+4+1。
- 典型应用：跳表、RMQ 区间最值、LCA 爬树、快速幂。
- 快速幂把指数拆二进制，底数自乘翻倍 → 时间复杂度 O(log e)。
- 看到「翻倍」「2^k」「二进制位」这些关键词，就想到倍增法。
🎮
学完了？来闯关！
下面 15 个小挑战，点一点就能玩
Demo 原型 · 每个知识点独立页面 · 暂不含真实编译与进度存储。