疯子的算法总结12--倍增

最近发现倍增讲的很少，这可以理解为二分新姿势！

我们设想一个背景，公主被邪恶的王八抓走了，马里奥大叔这次要去救公主了，如果他到的不及时公主就要被杀死了，他能抱得美人归吗？马里奥有一种神奇的能力，它可以在一秒钟之内走任意距离！已经知道了王八城堡很高，在哪里都能看见！

憨批马里奥：地球是圆的，我向相反的方向走，额。。。走多少米呢？不知道唉，于是他走了N圈地球后公主被杀了。

淳朴马里奥：我每次直走一米，我一定不会错过，那我每次走两米，也不会错过太多，那要是我一开始走三步，然后走一步也不会超过太多，到底怎么走呢？只能摸索的前进了，过了倒回来，于是公主也被杀了。

倍增马里奥：我第一次走1米，第二次我走2米，第三次我走4米。。。。。。。第N我走2^(n-1)米，要是我走过了那么我会在少走一半，要是在多走，我会回去少走一半，那么 次方式 的增长所需要时间绝对是少的，于是他拯救公主成功了，怎么成功的呢？我们看看他的策略：

虽然在这里我们还是觉得他的操作次数太多了，但是当这个距离很长的时候，按指数倍增长后 的次数不会多很多，就像1000最大也不过是9+9步，其实没这么多10步多一点，这时候倍增的好处就体现出来了。

关于倍增比较基础的算法就是ST表，静态RMQ算法：戳这里