Skip to content

倍增 Binary Lifting

倍增是一个很通用的基础算法，将线性的处理转化为对数级的处理，优化时间复杂度。

倍增的主要实现通过预先计算的“指针表”来完成，基本步骤分成预处理和实际计算两步：

  1. 预处理：预先计算指针表，比如在树上用倍增来跟踪祖先时，我们可以计算：每个节点的上一辈祖先，上两辈祖先，上四辈祖先，上八辈祖先，…，上\(2^k\)辈祖先。
  2. 实际计算：类似二分查找，从最远的指针开始尝试（可以理解成从高位开始依次尝试改变二进制位），逐步接近要计算的结点。

具体应用包括RMQ、LCA、最小瓶颈树等。

代码实现可以看LCA中倍增的使用。

习题