0x06 倍增
倍增，字面意思就是 “成倍增长”。
这是指我们在进行递推时，如果状态空间很大，通常的线性递推无法满足时间与空间复杂度的要求，那么我们可以通过成倍增长的方式，只递推状态空间在 $2$ 的整数次幂位置上的值作为代表。
当需要其他位置上的值时，我们通过 “任意整数可以表示成若干个 $2$ 的次幂项的和” 这一性质，使用之前求出的代表值拼成的所需的值。
所以倍增算法也要求我们递推的问题的状态空间关于 $2$ 的次幂具有可划分性。
“倍增” 与 “二进制划分” 两个思想互相结合，降低了求解很多问题的时间与空间复杂度。
我们之前学习的快速幂其实就是 “倍增” 与 “二进制划分” 思想的一种体现。
试想一个这样的问题：
给定一个长度为 $N$ 的数列 $A$，然后进行若干次询问，每次给定一个整数 $T$，求出最大的 $k$，满足 $\sum_{i = 1}^k{A[i] \leq T}$。你的算法必须是在线的（必须即使回答每一个询问，不能等待收到所有询问后再统一处理），假设 $0 \leq T \leq \sum_{i = 1}^N{A[i]}$。
最朴素的做法当然是从前向后枚举 $k$，每次询问花费的时间与答案的大小有关，最坏情况下为 $\mathcal{O}(N)$。
如果我们能够先花费 $\mathcal{O}(N)$ 的时间预处理 $A$ 数组的前缀和数组 $S$，就可以二分 $k$ 的位置，比较 $S[k]$ 与 $T$ 的大小来确定二分上下界的变化，每次询问花费的时间都是 $\mathcal{O}(\log{N})$。
这个算法在平均情况下表现很好，但是它的缺点是如果每次询问给定的整数 $T$ 都非常小，造成答案 $k$ 也非常小，那么该算法可能还不如从前往后枚举更优。
我们可以设计这样一种倍增算法。
- 令 $p = 1$，$k = 0$，$sum = 0$。
- 比较 “$A$ 数组中 $k$ 之后的 $p$ 个数的和” 与 $T$ 的关系，也就是说，如果 $sum + S[k + p] - S[k] \leq T$，则令 $sum$ $+=$ $S[k + p] - S[k]$，$k$ $+=$ $p$，$p$ $*=$ $2$，即累加上这 $p$ 个数的和，然后把 $p$ 的跨度增长一倍。
如果 $sum + S[k + p] - S[k] > T$，则令 $p$ $/=$ $2$。 - 重复上一步，直到 $p$ 的值变为 $0$，此时 $k$ 就是答案。
这个算法始终在答案大小的范围内实施 “倍增” 与 “二进制划分” 思想，通过若干长度为 $2$ 的次幂的区间拼成最后的 $k$，时间复杂度级别为答案的对数，能够应对 $T$ 的各种大小情况。
【例题】Genius ACM
ST 算法
在 RMQ 问题（区间最值问题）中，著名的 $ST$ 算法就是倍增的产物。
给定一个长度为 $N$ 的数列 $A$，ST 算法能在 $\mathcal{O}(N \log{N})$ 时间的预处理后，以 $\mathcal{O}(1)$ 的时间复杂度在线回答 “数列 $A$ 中下标在 $l \sim r$ 之间的数的最大值是多少” 这样的区间最值问题。
一个序列的字区间显然有 $O(N^2)$ 个，根据倍增思想，我们首先在这个规模为 $\mathcal{O}(N^2)$ 的状态空间里选择一些 $2$ 的整数次幂的位置作为代表值。
设 $F[i, j]$ 表示数列 $A$ 中下标在子区间 $[i, i + 2^j - 1]$ 里的数的最大值，也就是从 $i$ 开始的 $2^j$ 的子区间的最大值是左右两半长度为 $2^{j - 1}$ 的子区间的最大值中较大的一个。
void ST_prework() {
for (int i = 1; i <= n; i++) f[i][0] = a[i];
int t = log(n) / log(2) + 1;
for (int j = 1; j < t; j++)
for (int i = 1; i <= n - (1<<j) + 1; i++)
f[i][j] = max(f[i][j-1], f[i + (1<<(j-1))][j-1]);
}
当询问任意区间 $[l, r]$ 的最值时，我们先计算出一个 $k$，满足 $2^k \leq r - l + 1 < 2^{k + 1}$，也就是使 $2$ 的 $k$ 次幂小于区间长度的前提下最大的 $k$。
那么 “从 $l$ 开始的 $2^k$ 个数” 和 “以 $r$ 结尾的 $2^k$ 个数” 这两段一定覆盖了整个区间 $[l, r]$，这两段的最大值分别是 $F[l, k]$ 和 $F[r - 2^k + 1, k]$，二者中较大的那个就是整个区间 $[l, r]$ 的最值。
因为求的是最大值，所以这两段只要覆盖区间 $[l, r]$ 即可，即使有重叠也没关系。
int ST_query(int l, int r) {
int k = log(r - l + 1) / log(2);
return max(f[l][k], f[r - (1<<k) + 1][k]);
}