本课时有配套视频讲解，购买后即可观看（永久有效）

倍增法

一、课上练习

倍增法的核心思想是每次把问题规模翻倍。通过以2的幂次进行跳跃式处理，倍增法能够将原本需要线性时间的操作优化到对数时间复杂度，从而大幅提升算法效率。

倍增法通常用于解决以下类型的问题：

查询问题：对于如最小公共祖先（LCA）查询、区间最值查询等问题，倍增法能够快速跳过大量元素，达到快速查询的目的。
距离和路径问题：在图的路径查询中，如求解从一个节点出发到达任意节点的最短路径问题，倍增法可以通过预处理每个节点的"跳跃"信息（如跳1步、2步、4步…2^k步到达的节点），来快速计算出任意两点之间的最短路径或最小代价。
字符串和数组处理：在字符串匹配或数组中的查询问题，倍增可以用于构建高效的数据结构，如后缀数组和最长公共前缀（LCP）数组。

倍增法的基本解题思路是：从大到小尝试2的幂次跳跃，逐步逼近目标。具体来说，先尝试跳跃最大的步长（如2^k），如果跳跃后超出范围或不满足条件，则尝试更小的步长（2^(k-1)），依此类推，直到找到精确的答案。这种方式类似于二分搜索的思想，但更加灵活，适用于更广泛的场景。

以"在有序数组中查找第一个大于等于 target 的位置"为例，展示倍增法的执行过程。

数组 a[] = {1, 3, 5, 7, 9, 11, 15, 20, 25, 30, 35, 40, 50, 60, 70, 80}（共16个元素），target = 22。

第一阶段：倍增确定范围

从位置 0 开始，每次将步长翻倍，找到一个包含答案的区间：

步骤	当前位置 pos	步长 step	跳到 pos+step	a[pos+step]	与target比较	操作
1	0	1	1	a[1]=3	3 < 22	跳跃，pos=1
2	1	2	3	a[3]=7	7 < 22	跳跃，pos=3
3	3	4	7	a[7]=20	20 < 22	跳跃，pos=7
4	7	8	15	a[15]=80	80 >= 22	不跳，范围确定为 [7, 15]

第二阶段：从大到小尝试跳跃

现在从 pos=7 开始，步长从 4 开始逐步减半：

步骤	当前pos	步长	跳到	a[跳到]	与target比较	操作
1	7	4	11	a[11]=40	40 >= 22	不跳
2	7	2	9	a[9]=30	30 >= 22	不跳
3	7	1	8	a[8]=25	25 >= 22	不跳

最终 pos=7，a[7]=20 < 22，所以第一个 >= 22 的位置是 pos+1 = 8，a[8]=25。

整个过程只比较了 7 次，远少于线性搜索的 9 次。

使用倍增法解题时：

倍增法与二分搜索的区别：