关于倍增思想的几点总结

本文主要是介绍关于倍增思想的几点总结，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

倍增思想的概念：

每次通过倍增加速状态转移、预处理或查询（很多时候能把时间复杂度降到O(logN)）

倍增的注意事项：

在理解倍增之前，个人建议先对二进制有一定的理解
有时候要注意一下预处理的过程，不要出问题

倍增思想的例题（难度从低到高）：

P2886 [USACO07NOV]牛继电器Cow Relays
P1081 开车旅行（省选 NOI-）

倍增思想的适用范围（个人整理）：

在变化规则相同的情况下加速状态转移（如：快速幂，LCA（倍增法））
加速区间操作（如：ST表，后缀数组）

关于倍增思想的总结：

兔子跳：很多时候，倍增思想的使用过程就像兔子跳跃的过程一样（设兔子单次跳跃的距离为 $d$ ，假设在每次跳跃完成后， $d=d^2$ ）.学习这只兔子的跳跃过程，我们就可以尝试把极高的时间复杂度优化成 $O(n{log_{2}}^{n})$ .
对数据查询的优化：倍增很多时候是在查询过程中使用的（单次查询的时间复杂度通常为O（1）至 $O({log_{2}}^{n})$ .在查询速度优化的同时，往往也需要对数据的预处理.（预处理往往需要至少 $O(n{log_{2}}^{n})$ 的时间复杂度）
图论：在大多数情况下，图论中的点或边都可以按某种方式排序.如果问题的解要求O（NlogN）的时间复杂度，可以考虑倍增思想.在使用倍增思想的情况下，可以结合DP的"最优子结构"和ST表的思想尝试求解.
DP 记忆化：倍增很多时候也需要借用DP的"记忆化"思想，从而在查询中以下标代表2^i的方式进行查询.
爆炸：使用倍增的优化方式往往可以爆炸性的优化程序的运行速度（比如：从 $O(2^{n})$ 优化到 $O(n{log_{2}}^{n})$ ）
二进制：在许多情况下，倍增的具体实现与二进制运算有关.在使用倍增思想的过程中，往往可以结合二进制进行考虑.比如：尝试使用位运算优化状态转移.（如：（1<<i）在ST表和倍增求LCA中的应用和（i=i>>1，i&1）在快速幂中的应用）
加速DP状态转移：有时候可以使用倍增的方法优化DP（如：快速幂），使用这种方法可以参考快速幂的实现.（关于使用倍增思想加速DP状态转移可以参考《浅析倍增思想在信息学竞赛中的应用》）