指数提升（倍增，Binary Lifting）

Algorithm

November 16, 2022

前言

我一定要狠狠地“表扬“一下“倍增“这个翻译，这个翻译从字面上看是要翻倍、增加，可是翻倍已经包含增加的内涵（一般概念上的对象都是自然数的），结果实际上一般人看到这个词就只能理解到翻倍的意涵，为什么要翻倍？这么做的好处在哪儿？这到底是什么东西？我每次看到这个词总是一头雾水，看了几次算法介绍也不能抓到关键点，而使用倍增这个翻译的介绍的大多数作者也没能抓住关键点，可能他们也被倍增这个鬼翻译迷惑住，只能硬讲流程，却点不出关键点。

我是直到看到“倍增”对应的英文词 Binary Lifting ，才恍然大悟，明白它的想法到底是什么，什么叫“好“翻译增加学习曲线的陡峭度？！它显然是可类比 Binary Search 二分搜索，用指数级别增长取代线性增长概念，从而把线性时间复杂度降低为对数级时间复杂度。这又要讲这个鬼翻译，大哥你提升和增长哪个更形象？你不觉得增长过于抽象了吗？何况你又把增长缩写为“增“，很可能人一看到“增“首先联想到的是增加而不是增长，那增加就比增长更抽象了，最后更绝地是，翻译者觉得“倍增”就是把翻倍和增长结合在一起的意思，这完全没有语文素养，没意识到白话文双元词语义分主辅的使用习惯，比如“强力”，主要是“强”，“力”是对“强”的辅助修饰，而倍增一词，就是一个“倍“，增通常是辅助，是被忽略的！

这样我们分析了“倍增”如何犯了一系列模糊重点，翻译失准的问题，翻译三重标准–信达雅，翻译者可能觉得自己这种翻译简直“既达而雅”了，实际在第一步“信“的标准上就失败了（很多那些让人摸不着头脑的翻译比那些佶屈聱牙的直白翻译还不如）（按照这种翻译，二分搜索就可以翻成“半搜“了，让人看了也一头雾水）。

所以我自己使用了一个更到位，让人一眼就看清楚这个算法是做什么的直白翻译：指数提升 ，这个翻译首先从全局上讲清楚了，就是指数级增长，然后是“提升“就比“增“具体地多，清楚得多。

算法思想

指数提升在前言里已经提过了，就是用指数级增长取代线性增长，这里我们具体地描述一下场景：

假设有在同一直线上的两点 $A$ , $B$ ，在不知道 $\vert AB \vert$（$A$ 到 $B$ 的距离）的情况下，从 $A$ 跳到 $B$ ，每次跳幅是单位距离的整数倍。

我们有如下几个逐渐改进的方案：

步行

一个单位一个单位的跳，每次检查是否到了 $B$ 点，这肯定可以，但这是最慢的方法。

传统家用汽车

一跳跳固定跳 $n$ 个单位，最后距离如果不足一跳就下车步行（改为一个单位一个单位跳）

比步行强多了，但控制太差，要么速度不够快，要么步行距离长。

传统超跑

前面两种方法本质都是 $O(n)$ 的时间复杂度，于是我们想，可以加快这一过程，用指数增长（或减少）的步幅来跳。

假设幂底是 $m$ ，用档位代指指数，那么 $n$ 档就是 $m^n$ 。

这样我们从 $0$ 档起步，每跳一步，就加速一档： $1$ 档, $2$ 档, ……, $n$ 档，直到第 $n+1$ 步会超过 $B$ ；
之后从 $n$ 档开始逐一降档，直到下一步不超过 $B$ ，然后尝试保持档位跳第 $n+2$ 步，仍然超过就继续降档，重复步骤2，直到降到 $0$ 档，然后下车步行，直到到达 $B$ 点

有了指数级变速器，这比传统家用汽车性能强多了，但显然一档一档地提速显得加速度不够理想。

电动超跑

假如我们知道 $\vert AB \vert$ 最大不超过 $x$ ，那么我们可以起步挂在 $\lfloor \log_{m}x \rfloor$ 档，一步到位，之后直接进入步骤2。

在最后的电动超跑的方案下，挂在每档的次数，对应相应位上的数字，这样从高到低，构成了 $\vert AB \vert$ 的 $m$ 进制表示。设挂在每档的次数为 $k$ , 则显然有 $0\leqslant k < m$ 。

通常我们会设定 $m=2$ ，这有实现上的便利：

当 $m=2$ 时，$k \in [0, 1]$，这意味着不存在重复的档位，挂了 $n$ 档后，下一步直接从 $n-1$ 档开始检查，当挂完 $0$ 档之后，一定到达了目的地；
可以直接通过右移（right shift）来做 $2$ 为底的对数运算

所以我们还可以把“指数提升“叫做幂（指）2提升或二进制提升，无论它们哪一个名字都比倍增要好得多。

vs 二分搜索

Binary Lifting 和 Binary Search ，两者有很多微妙的相同点与不同点，两者适用的问题是有一定重合的，但是：

借用 LCA 的场景，二进制提升可以方便地预处理每个位置的指数级祖先，而二分搜索没有预处理的选项，或者说二分搜索如果要有，实际上就是分段树的模样；
从风味上，二分搜索一定要有一个三元结果的比较：小于、等于和大于，而二进制提升则只考虑超过了目标或者没超过目标，当然这只也只是使用风味上的区别，两者可以互相转化；
因此可以说，二进制提升在概念上比二分搜索更高一些，相当于二分搜索+分段树

应用模板

快速开对数（2为底）

fn quick_log2(x: i32) -> i32 {
    let mut n = 0

    while x > 0 {
        x >>= 1;
        n += 1;
    }

    n
}

开跳

for i in (0..quick_log2(x)).rev() {
    // skip 2^i
}