倍增法

课上练习

• 倍增查找问题1：L3151

测试数据：

• 倍增查找问题2：L3152

测试数据：

知识总结

倍增法-知识总结

倍增法-知识总结 核心思想 每次把问题规模翻倍！

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

解题思路 把问题规模翻倍进行求解。

️课后作业

☝️总结作业

总结作业非常重要，请务必认真完成✔️

• 简单总结倍增法的核心思想。

✌️编程作业

考试只有一次提交机会，请务必本地检查正确后再提交❇️

• 查找最接近的元素：L3153