1. 倍增思想

任意整数均可表示成若干个2的次幂项的和。例如，整数5，其二进制位101，该二进制数从右侧向左，第0，2位均为1，那么 5 = 2^2 + 2^0; 整数26，其二进制数表示为11010，该二进制数从右侧向左，第1，3，4 位均为1，那么 26 = 2^4 + 2^3 + 2^1。也就是说2的次幂项可以拼成任何一个需要的值。

(资料图片仅供参考)

倍增，顾名思义，就是成倍的增长。如果问题的状态空间特别大，一步一步的递推算法复杂度太高，可以通过倍增思想，只考察2的整数次幂位置，快速缩小求解范围，直到找到所要的解。

例如，一颗树中，每一个结点的祖先均比该结点大，查找4的祖先中等于 x 的祖先结点。最笨的办法就是一个一个的向上比较祖先结点，判断哪一个等于 x ，如果树特别大，搜索的效率很低。虽然祖先具有有序性，但是不是顺序存储，无法得到中间结点的下标，因此不可以采用普通的二分搜索，怎么办呢？

采用倍增的思想：

x和当前结点向上 2^0个结点比较，如果 x 大于该结点，则向上跳 2^0个结点；

x和当前结点向上 2^1个结点比较，如果 x 大于该结点，则向上跳 2^1个结点；

x和当前结点向上 2^2个结点比较，如果 x 大于该结点，则向上跳 2^2个结点；

...

x和当前结点向上 2^k个结点比较，如果 x 小于该结点，则锁定搜索范围，减少增量继续搜索：

x和当前结点向上 2^(k-1) 个结点比较，如果 x 小于该结点，则锁定搜索范围，减少增量继续搜索：

x和当前结点向上 2^(k-2) 个结点比较，如果 x 大于该结点，则向上跳 2^(k-2) 个结点；

从当前结点出发，继续搜索，直至找到该结点，查找成功，或增量减为 2^0 仍不相等，查找失败。

也就是说， x 和当前结点向上 2^i 个结点比较，如果 x 大于该结点，则向上跳 2^i 个结点，加大增量 2^(i+1) ,继续比较； 如果 x 小于该结点，则减少增量 2^(i-1)，继续比较； 直到相等返回查找成功，或增量减为 2^0仍不相等，查找失败。

2. 稀疏表(ST)

稀疏表（Sparse Table, ST）算法是采用倍增的思想， 在 O(n logn) 的时间构造一个二维表之后，可以在 O(1) 的时间在线查询区间 [ l, r ] 的最值。 ST 算法可以有效的解决在线 RMQ问题（区间最值查询）。

怎么实现呢？

设 F[i，j] 表示区间 [ i, i+2^j-1] 的最值，区间长度为 2^j , 如图所示：

根据倍增思想，区间长度为 2^j 可以分成两个区间长度为 2^(j-1) 的子区间，然后求两个子区间的最值即可。

递推公式：F[i，j] = max( F[ i, j-1], F[i + 2^(j-1),j-1])

（1）ST 表创建

F(i,j) 表示区间 [ i, i+2j-1] 的最值，区间长度为 2^j，那么 i 和 j 的取值范围是多少呢？

如果数组的长度 n，最大区间长度 2^k <= n <= 2^(k+1)， 则 k = [ log2 (n) ]，例如 n = 8,则 k = 3; n=10,则 k = 3。在程序中， k = log2 (n), 也可以用通用表达式 k = log(n)/log(2),其中log()表示以 e 为底的自然对数。

区间长度： 2^0, 2^1, 2^2, ..., 2^k, j = 0,1, ..., k 。

起点 i ：1, 2, ..., n-2^j +1, i = 1,2, ..., n-2^j +1。

初始化， F[ i, j ] = a[ i ] ,表示区间 [ i, i ] 的最值，区间长度为 2^0。

算法代码：

例如，有 10 个元素 a[ 1 ... 10] = { 5, 3, 7, 2, 12, 1, 6, 4, 8, 15}，其查询最值的ST表如图所示。 F[ i, j ] 表示区间 [ i , i+ 2^j -1 ] 的最值，区间长度为 2^j。

（2）ST表查询

如果查询区间 [ l,r] 的最值，首先计算 k 值，和前面的计算方法相同，查询区间长度为 r-l+1, 2^k <= r-l+1 < 2^(k+1) ，因此， k = log2( r-l +1 ) 。

查询区间长度大于等于 2^k , 小于 2^(k+1) ， 那么根据倍增思想，可以将查询区间分为两个查询区间，取两个区间的最值即可。两个区间分别为从l 向后的 2^k 个数，从 r 向前的 2^k 个数，这两个区间有可能有重叠，但对求最后没有影响。如图所示。

算法代码：

（3）ST算法性能分析

标签：