<!--markdown--># 倍增法（快速幂 & ST 表）
引入
求 2^1000000 的个位数？如果老老实实乘 100 万次肯定超时。快速幂能在 O(logn) 内算 a^n。而求一段区间的最值，每次都扫一遍是 O(n)，用 ST 表（Sparse Table） 能预处理后在 O(1) 回答。它们背后的共同思想，就是倍增：把一次大步拆成多个「翻倍的小步」，用预处理好的「2 的幂次」结果拼出答案。
---
一、快速幂（Fast Pow）
1. 思路
把指数 n 写成二进制，例如 n = 13 = 1101₂ = 8+4+1，那么：
a^13 = a^8 × a^4 × a^1
我们只需不断把 a 自己翻倍（a → a² → a⁴ → a⁸），再根据 n 的二进制位决定乘不乘当前这个翻倍结果。这样最多乘 log n 次。
2. 代码
cpplong long fastPow(long long a, long long n, long long mod) {
long long res = 1;
a %= mod;
while (n > 0) {
if (n & 1) res = res * a % mod; // 当前二进制位是 1，乘上
a = a * a % mod; // a 自己翻倍
n >>= 1; // n 右移一位
}
return res;
}
- 复杂度
O(logn)。 - 常配合取模，防止溢出。
3. 应用
- 求
a^n mod p。 - 矩阵快速幂：求斐波那契第 n 项
F(n)（用转移矩阵的 n 次幂）。 - 模运算下的逆元（配合费马小定理）。
---
二、ST 表（稀疏表）——区间最值 RMQ
1. 思想
预处理出所有长度为 2 的幂的区间的最值。st[i][j] 表示从 i 开始、长度 2^j 的区间最值。任意区间 [L,R] 的最值，可以由两个长度为其「最大不超过区间长的 2 的幂」的区间重叠拼出。
2. 预处理与查询
cpp// st[i][j]：以 i 为起点、长度 2^j 的区间最值（这里以最大值为例）
int log2s[N];
int st[N][LOG];
void build(int n, int a[]) {
for (int i = 1; i <= n; i++) st[i][0] = a[i];
for (int j = 1; (1 << j) <= n; j++)
for (int i = 1; i + (1 << j) - 1 <= n; i++)
st[i][j] = max(st[i][j-1], st[i + (1 << (j-1))][j-1]);
}
int query(int L, int R) {
int k = log2s[R - L + 1]; // 最大的 2^k <= 区间长
return max(st[L][k], st[R - (1 << k) + 1][k]); // 两块重叠覆盖整个区间
}
- 预处理
O(nlogn)，单次查询O(1)。 - 只能处理静态数组（不可修改），适合只查不改的 RMQ。
---
三、倍增的其他应用（竞赛常见）
- 树上倍增求 LCA：预处理每个点向上跳
2^j步到的祖先，查询时按二进制位跳。 - 二分答案的验证中的倍增跳跃、稀疏图上的可达查询。
- 核心思想：「跳一步」分解成「跳多个 2 的幂」，用预处理省时间。
---
四、考点提示
- 快速幂完善题：
if(n&1) res=res*a%mod;、a=a*a%mod、n>>=1三行填空高频。 - ST 表：
k = log2(len)、max(st[L][k], st[R-2^k+1][k])的写法、st[i][j] = max(st[i][j-1], st[i+2^(j-1)][j-1])。 - 判断题：ST 表不可修改数据；快速幂时间复杂度是
O(logn)而非O(n)。
一句话记忆：倍增 = 用「翻倍的步长」预处理 + 按二进制拼答案；快速幂算次幂、ST 表答区间最值、树上倍增找 LCA，全是它的应用。