倍增

数学定义

• 数值倍增：每次操作使数值变为原来的两倍，如 a_n = 2ⁿ（几何级数增长）。

• 函数倍增：若 f(n) = O(2ⁿ)，称其具有指数时间复杂度。

计算机科学中的倍增法

• 预处理：通过存储不同“步长”的信息（如 2^k 步后的状态），将多次查询的耗时从 O(n) 降至 O(log n)。

• 分治策略：将大问题分解为多个倍增的子问题，逐步合并结果。

1. 算法优化

最近公共祖先（LCA）

• 问题：在树结构中快速找到两个节点的最近公共祖先。

• 倍增法步骤：

  1. 预处理每个节点向上 2^k 层的祖先（k = 0, 1, 2...）。

  2. 查询时通过二进制跳跃调整两节点深度，逐级逼近LCA。

• 时间复杂度：预处理 O(n log n)，单次查询 O(log n)。

范围最值查询（RMQ）

• 问题：快速获取数组中区间的最小/最大值。

• ST表（Sparse Table）：

  • 预处理每个起点 i 的 2^j 长度区间的最值。

  • 查询时选取覆盖区间的最长 2^k 块，合并结果。

2. 快速幂算法

• 问题：高效计算 a^b mod p（大指数运算）。

• 倍增思想：将指数 b 转为二进制，逐位计算 a^2k 并累乘。

• Python代码示例：

  def fast_power(a, b, p):
      result = 1
      while b > 0:
          if b % 2 == 1:
              result = (result * a) % p
          a = (a * a) % p
          b = b // 2
      return result

• 时间复杂度：O(log b)，远优于朴素算法的 O(b)。

3. 网络传输（TCP拥塞控制）

• 慢启动机制：

  • 初始拥塞窗口（cwnd）为1 MSS（最大报文段）。

  • 每收到一个ACK，cwnd倍增，直至达到阈值或出现丢包。

  • 目的：快速探测可用带宽，避免网络过载。

倍增法通过预处理和二进制跳跃，将时间复杂度从线性降至对数级，是计算机科学中优化算法的有力工具。其思想不仅限于树结构和区间查询，还广泛应用于字符串匹配、网络协议、数值计算等领域。随着大数据和分布式系统的发展，倍增法在并行处理和高效计算中仍具有重要价值。