一、什么是倍增
倍增法(binary lifting)，顾名思义就是翻倍。它能够使线性的处理转化为对数级的处理，大大地优化时间复杂度。
这个方法在很多算法中均有应用，其中最常用的是：RMQ问题和求LCA (最近公共祖先)。
倍增思想是一种十分巧妙的思想。“倍增”二字体现在它每次将当前的已知结果或考察范围扩大一倍。正是由于这个原因，它的时间复杂度降低了很多，一般是将一个系数N变为 log2N。
二、倍增思想举例
例子1： 寻找2的幂，体现了倍增的思想。
如果要求比n小的最近的2的幂，2(int)log2n ,这个值，是从1开始跳跃 (int)log2n 次得到的。
例子2：
如何用尽可能少的砝码称量出［0,31］之间的所有重量？(只能在天平的一端放砝码)
答案是使用1 2 4 8 16这五个砝码，可以称量出 之间的所有重量。同样，如果要称量之间的所有重量，可以使用1 2 4 8 16 32 64这七个砝码。每次我们都选择2 的整数次幂作砝码的重量，就可以使用极少的砝码个数量出任意我们所需要的重量。
可以发现，我们的目标量翻倍的情况下，我们需要的砝码数量只需要+1。
例子3：
有非负整数数列：al a2 a3 a4 a5 … an,有M次询问，每次需要求：不超过给定的整数 Ti 的最大的前缀和。
求解思路：预处理前缀和，倍增思想跳跃取值。
三、RMQ问题
RMQ (Range Maximum Query)用于求静态区间最大值(也可以求最小值)。
ST表(Sparse Table,稀疏表)实现RMQ可以做到：O(n*logn)的预处理，O(1)的时间复杂度查询。一般用于多次询问RMQ的问题。特别要注意：ST的算法条件是数组本身不能有修改。
ST表是用于解决 可重复贡献问题 的数据结构。
RMQ的求解思想
以每个点为左端点，求出长度为2len的区间最大值。左端点的选择有n种，长度的选择 有：1 2 4 … 2log2n ，也就是n * log2n种需要讨论的状态。
这里釆用 DP+倍增 的思想求出从每个点开始的区间长度为2len的区间最值。
第一步：求ST表
f(i,j)：表示从i开始，长度是2j的区间中的最大值。
比如：f(1,3)，代表从1开始，长度为8的区间［1,8］的最大值。
第二步：区间询问
询问[L,R]之间的区间最值：求出最大的k，使得 2k<=R-L+1。
注意：为提升求log的效率，可以预处理log2(n)的值。
四、倍增应用:树上倍增——倍增求LCA