倍增

在解决一个大问题的时候，我们常常将其分解为多个与大问题结构相同的小问题后分别求解，再将小问题的答案分析汇总成大问题的答案．但如果现在有很多件大问题摆在面前，对现场每个大问题分解成小问题，然后再解决现场的小问题，未免有些力不从心．我们渴望在此之前预处理小问题的答案，然后现场调用直接得到小问题的答案，而无需现场求解小问题．那么问题来了，在遇到大问题之前，如何设计小问题之间的结构，以便求解大问题时拆解成自己构造的子问题？ 二进制的倍增思想或许能为我们解答．

引入 ​

在第一个世界上，货币的面值只有 1 元，A 要以现金给 B 转账，但 B 没告诉 A 要转多少，B 只能说 A 转的钱多了还是少了，A 知道 B 最多要 3000 元．A 当然有二分思想，但他很烦，因为他只有面值为 1 元的纸币，需要带足很多张 1 元纸币才能确保万无一失，但钱包空间是有限的（现场求解小问题会消耗时间）．

在第二个世界上，货币的面值有 1 元，2 元，3 元，4 元 …… 一直到 10 元 (小问题预处理后的答案，如 3 元 = 1 元 + 1 元 + 1 元）．不用多说，这种面值的安排非常笨，光是设计这 10 种 ($O(n)$) 面值的纸币是个不小的工程量（如果预处理一个小问题需要消耗 $O(n)$ 的时间，那么预处理所有小问题需要消耗 $O(n^2)$ 的时间，并且各个小问题的结构不合理，导致大问题拆解后，小问题的数量依旧不少)．

A: 10 元
B: 不够
A: 20 元
B: 不够
…
A: 1440 元
B: 不够
A: 1450 元
B: 多了
A: 1445 元
B: 多了
A: 1442 元
B: 正好
(147 次询问)

在第三个世界上，货币的面值有 1 元，2 元，4 元，8 元 …… 一直到 1024 元．和第二个世界比，这种就合理多了：同样是设计 10 种 ($O(\log n)$) 面值的纸币，任何金额在这种方案下只使用了很少的纸币 ($O(\log n)$)．(相比第二个世界，这里预处理只需消耗 $O(n \log n)$ 的时间)

A: 2048 元
B: 多了
A: 1024 元
B: 少了
A: 1024 + 512 元
B: 多了
A: 1024 + 256 元
B: 少了
A: 1024 + 256 + 128 元
B: 少了
A: 1024 + 256 + 128 + 64 元
B: 多了
A: 1024 + 256 + 128 + 32 元
B: 少了
A: 1024 + 256 + 128 + 32 + 16 元
B: 多了
A: 1024 + 256 + 128 + 32 + 8 元
B: 多了
A: 1024 + 256 + 128 + 32 + 4 元
B: 多了
A: 1024 + 256 + 128 + 32 + 2 元
B: 正好
(11 次询问)

倍增 ​

可拆性与合并性 ​

在引入部分，某一金额能够被拆成不同面值纸币的价值，不同面值纸币的价值就是预处理后小问题的答案．从中我们可以看出，倍增思想的使用前提是相似小问题的答案能够合并成大问题的答案，或者大步骤能够被线性拆解成相同小步骤．

欲求解 $7^{397}$ 这个大问题，可以将其拆解成若干相似小问题

$$7^{397} = 7^{114} \cdot 7^{51} \cdot 7^{41} \cdot 7^{91} \cdot 7^{19} \cdot 7^{81} \cdot 7^0$$

这些小问题的答案能够合成出大问题的答案．

欲求解数组 arr $[114, 514]$ 上的最小值，可以将其拆解成若干相似小问题：分别求解

$$[114, 191], [192, 389], [390, 442], [443, 514]$$

上的最小值，这些小问题的答案能够合成出大问题的答案．

欲求在给定若干互不包含且能覆盖环的区间下，某一区间必须被选，此时能覆盖整个环的最少区间数．
先按区间起始端给区间排序，然后化圆为线，根据贪心，第一步先选上给定的必选区间，此后某一区间若被选上，则下一选上的区间是：左端点最靠近上一选上区间右端点的区间．这一贪心方案直至选出的区间总覆盖长度首次超过环长，此时选出的区间数即为答案．
从选出的第一个区间到选出的最后一个区间，一共选了 $k$ 个区间，相当于一共走了 $k$ 步，这 $k$ 步能够被拆解成若干阶段 (相似小步骤能够合成大步骤)．

倍增标尺与进制 ​

在遇到实际的大问题前，我们想要预处理所有自己构造出来小问题．在思考如何预处理之前，我们发现小问题长啥样都不知道，那还咋预处理？我们需要设计出这些小问题的结构 (犹如设计一把尺子的刻度，保持测量“精度”的同时，刻度越少越好)，像引入部分第二个世界那样线性地设计显然是不可取的，我们倍增地设计．

在快速幂中，欲求解 $7^{397}$，我们设计倍增标尺： $7^1, 7^2, 7^4, 7^8, 7^{16}, 7^{32}, \cdots$，于是

$$7^{397} = 7^{256} \cdot 7^{128} \cdot 7^8 \cdot 7^4 \cdot 7^1$$

这个大问题被我们设计的倍增标尺度量了出来，也就是这个大问题已经拆解成我们想要的相似小问题．

在 ST 算法下的 RMQ 问题里，欲求解数组 arr 任意区间上的最小值，我们可以先为所有起点设计共 arr.length 把标尺：以任一位置为起点，长度分别为

$$1, 2, 4, 8, \cdots$$

的区间，此时 $[114, 514]$ 被拆成

$$[114, 114 + 255], [370, 370 + 127], [370, 370 + 127], [498, 498 + 15], [514, 514 + 0]$$

在国旗计划 (P4155) 中，从选出的第一个区间到选出的最后一个区间，一共选了 $k$ 个区间，相当于一共走了 $k$ 步．线性地走 $k$ 步，且在每一步检查覆盖长度是否超过环长，有点笨，于是我们为每一步到达的区间设计倍增的步长 $1, 2, 4, \cdots$，这样比如从第 $1$ 个区间出发 $27$ 步到达第 $28$ 个区间就可以分解成：
从第 $1$ 个区间出发的 $16$ 步，从第 $17$ 个区间出发的 $8$ 步，从第 $25$ 个区间出发的 $2$ 步，从第 $27$ 个区间出发的 $1$ 步．
至于在不知道要走 $27$ 步的情况下，从第 $1$ 个区间出发为啥先是 $16$ 步，这是因为已经尝试过 $32$ 步，但发现超了 (像引入部分那样，不知道目标金额，只知道多了少了)，于是选取下一刻度 $16$ 步．

我们发现这三个例子无不反映出二进制的倍增特点：

可拆性体现在任何数 $x$ 都能用二进制表示，且只需要用 $O(\log x)$ 个数位表示；

合并性体现在各位值的和就等于 $x$．

简便的预处理 ​

我们设计的倍增小问题该如何预处理答案呢？由于倍增这一过程的单调性，我们在求解较大的小问题时，能够调用较小的小问题的答案，从而可以使用递归求解．

按照倍增标尺将木棍一分为二，两段木棍长度一致．由于倍增这一过程的自我相似性，我们不需要递归，直接递推求解即可，因为递推方程并不复杂．

在倍增标尺 $7^1, 7^2, 7^4, \cdots$ 中，

$$7^{2^i} = \left(7^{2^{i-1}}\right)^2$$

于是我们可以先求解 $7^1$ 得到递推初始条件．

arr.length 把倍增标尺：以 $i$ 为起点，长度分别为 $2^j$ 的区间．这些区间上的答案设为 $\text{dp}[i][j]$．

$$\text{dp}[i][j] = \min (\text{dp}[i][j - 1], \text{dp}[i + 2^{j-1}][j-1])$$

等式右边只含 $j - 1$，可递推实现，递推初始条件为 $\text{dp}[i][1] = \text{arr}[i]$．

从第 $s$ 个区间出发，走 $2^k$ 步 (倍增标尺) 后到达的区间记为第 $\text{jump}[s][k]$ 个区间，则

$$\text{jump}[s][k] = \text{jump}[\:\:\text{jump}[s][k-1]\:\:][k-1]$$

拆解大问题 ​

我们使用倍增标尺去度量待求解的大问题，根据刻度读出已预处理的小问题并调用．

以 ST 算法为例

cpp

#define int long long
vector<T> arr(n);
vector<vector<T>> dp(n, vector<T>(__lg(n) + 2));
template <typename T>
T ST_init() {
  // 递推初始条件
  for (int i = 0; i < n; i++) {
    dp[i][1] = arr[i];
  }
  // 较大小问题拆成较小小问题
  for (int j = 1; (1 << j) <= n; j++) {
    for (int i = 0; i + (1 << j) - 1 < n; i++) {
      assert(i + (1 << (j - 1)) <= n);
      dp[i][j] = min(dp[i][j - 1], dp[i + (1 << j)][j - 1]);
    }
  }
}
template <typename T>
T RMQ(int L, int R) {
  int len = R - L + 1;
  // 因为是求区间最值，不用彻底拆成二进制的形式
  // 两把尺子相同间距的刻度能刚好覆盖全区间即可
  // 这里 2^{__lg(len)} 超过区间半长，但又不超过区间长
  return min(dp[L][__lg(len)],
             dp[R - (1 << __lg(len)) + 1][__lg(len)]);
}