稀疏表存储和查询

一 倍增

任意整数均可被表示成若干个 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的整数次幂位置，快速缩小求解范围，直到找到解。

例如，在一棵树中，每一个节点的祖先都比该节点大，要查找 4 的祖先中等于 x 的祖先节点。最笨的方法就是一个一个的向上比较祖先节点，判断哪一个等于 x。若树特别大，则搜索效率很低，虽然祖先是有序的，但不是按顺序存储的，无法得到中间节点的下标，因此不可以采用普通的二分搜索。这时怎么办？答案是采用倍增思想，将 x 和当前节点向上 2^i 个节点进行比较，若 x 大于该节点，则向上跳 2^i  个节点，加大增量 2^(i+1)继续比较，若 x 小于该节点，则写减少增量 2^(i-1)，继续比较，直到相等，返回查找成功，或者增量减 2^0 仍不相等，返回查找失败。

二 ST

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

F[i,j] 表示 [i,i+2^j-1] 区间的最值，区间长度为 2^j。

根据倍增思想，长度为 2^j 的区间可被分成长度为 2^(j-1) 子区间，然后求两个子区间的最值即可。递推公式：F[i,j]=max(F[ij-1],F[i+2^(j-1),j-1])。

三 ST 创建

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

若数组的长度为 n，最大区间长度 2^k<=n<2(k+1)，则 k 为 log2n 向下取整，比如 n = 8 时，k=3，n=10，则 k=3.

例如有 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。

F[1,0] 表示 [1,1+2^0-1] 区间，即 [1,1] 最值为 5，第 0 列为数组自身。

F[1,1] 表示 [1,1+2^1-1] 区间，即 [1,2] 最值为 5。

F[2,3] 表示 [2,1+2^3-1] 区间，即 [2,9] 最值为 12。

F[6,2] 表示 [6,1+2^2-1] 区间，即 [6,9] 最值为 8。

四 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 个数，这个区间可能有重叠，但对求最值没有影响。

五 代码

package com.platform.modules.alg.alglib.p35;
 
public class P35 {
    public String output = "";
 
    private final int maxn = 105;
    private int n;
    private int[] a = new int[maxn];
    // F(i,j) 表示区间 [i，i+2^j-1] 的最值，区间长度为 2^j
    private int F[][] = new int[maxn][maxn];
 
    void ST_create() {
        for (int i = 1; i <= n; i++)//初始化
            F[i][0] = a[i];
        int k = (int) Math.floor(Math.log(n) / Math.log(2));
        for (int j = 1; j <= k; j++)
            for (int i = 1; i <= n - (1 << j) + 1; i++)//n-2^j+1
                F[i][j] = Math.max(F[i][j - 1], F[i + (1 << (j - 1))][j - 1]);
    }
 
    int ST_query(int l, int r) // 求区间[l..r]的最值
    {
        int k = (int) Math.floor(Math.log(r - l + 1) / Math.log(2));
        return Math.max(F[l][k], F[r - (1 << k) + 1][k]); // 取两个区间最值
    }
 
    void ST_print() {
        int k = (int) Math.floor(Math.log(n) / Math.log(2));
        for (int j = 0; j <= k; j++) {
            for (int i = 1; i <= n - (1 << j) + 1; i++) // n-2^j+1,打印第一列
                output += F[i][j] + " ";
            output += "\n";
        }
    }
 
    public String cal(String input) {
        int l, r;
        int i, v;
 
        String[] line = input.split("\n");
        n = Integer.parseInt(line[0]);
 
        String[] words = line[1].split(" ");
 
        // 5 3 7 2 12 1 6 4 8 15
        for (i = 1; i <= n; i++) {
            a[i] = Integer.parseInt(words[i - 1]);
        }
 
        ST_create();//创建ST表
        ST_print();
 
        String[] bounds = line[2].split(" ");
        l = Integer.parseInt(bounds[0]);
        r = Integer.parseInt(bounds[1]);
        // 求区间[l..r]的最值
        output += "" + ST_query(l, r);
        return output;
    }
}

六 测试