目录
1. 倍增算法的思想
2. 倍增算法的应用
2.1 在变化规则相同的情况下加速状态转移
2.2 加速区间操作
2.3 倍增算法为何用2倍
1. 倍增算法的思想
倍增思想是一种十分巧妙的思想，它的本质思想是每次根据已经得到的信息，将考虑的范围扩大一倍，从而加速操作。
2. 倍增算法的应用
2.1 在变化规则相同的情况下加速状态转移
变化规则相同的意思：
- 每次的变化规则必须相同
- 变化规则必须满足结合律(加法，乘法)
快速幂算法
矩阵快速幂算法
DP+矩阵快速幂优化（状态有限）
倍增思想所作用的对象实际上是变化规则，而并非具体的状态！
倍增思想的作用是算出一个状态到另一个状态的变化量。也就是说，倍增思想计算出的量与具体的状态是无关的，而仅与状态之间的关系有关。
2.2 加速区间操作
一般RMQ问题（ST算法） 构造后缀数组（DA算法）
2.3 倍增算法为何用2倍
证明倍增量k>=3的时候为增函数，复杂度更高。因此k=2可以保证复杂度最低
一个数组只允许和开头或者末尾的数字交换，最终使得数组有序，问最多需要多少次交换？
