二维ST表学习笔记

众所周知，ST表是一种离线解决RMQ(区间最值)问题的方法。

可以在O(n \log {n} ) 的时间内进行预处理，然后在O(1)时间内查询到结果。

复习一维

我们先来复习一下，一维st表的预处理和查询过程。
对于预处理，我们先定义一个名为st的二维数组，其中st[i][j]表示以i为起点，从起点开始（含起点）往后2^j个元素的最值。

满足i+2^j-1不越界

因为2^0 = 1 ，因此st[i][0]=a[i]

然后我们用2个for循环去打表就行了

接着是查询，这里我画了个图来解释。

其中橙色的线表示两个区间。

一维代码

int st[50001][16];
int a[50001];//用于存储原有的数据
int pow2(int x) {
    return 1 << x;//相当于计算2的x次方，使用位运算
}
void init_st(int n) {
    for (int i=1;i<=n;i++) st[i][0]  = a[i];
    for (int j=1;pow2(j)<=n;j++) 
        for (int i=1;i+pow2(j)-1<=n;i++) st[i][j] = min(st[i][j-1],st[i+pow2(j-1)][j-1]);
}
int query(int l,int r) {
    int k = log2(r - l + 1);
    return min(st[l][k],st[r-pow2(k)+1][k]);
}
int main() {
    return 0;
}

二维ST表

接着是二维ST表

与一维ST表不同的是，我们这么定义数组。

int st[50001][50001][16][16];

那么，我们如何做预处理和查询呢。

预处理

显然，由于变成了4维数组，我们得把for循环写成这样

for (int i=0;i<=log2(n);i++)
    for (int j=0;j<=log2(m);j++) {
        if (i == 0 && j == 0) continue;
        for (int x=1;x<=n;x++) 
            for (int y=1;y<=m;y++) {
                // ....
            }

其中，st[x][y][0][0]为原来的值。

这里，我用i和j分别表示x和y方向的范围（以2为底的指数表示）

接着，我们想想，既然我们推的过程是

优先递增j，而后递增i

也就意味着，我们可以对i的值分类讨论

1. 对于i==0的情况，我们可以从i不变，j-1的状态转移

st[x][y][i][j] = max(st[x][y][ i ][j-1],st[     x     ][y+pow2(j-1)][ i ][j-1]);

2. 对于i>0的情况，我们可以从j不变，i-1的状态转移

st[x][y][i][j] = max(st[x][y][i-1][ j ],st[x+pow2(i-1)][     y     ][i-1][ j ]);

所以，最终的预处理代码就变成了这样

int pow2(int x) {
    return 1 << x;//相当于计算2的x次方，使用位运算
}
void init() {
    //st[x][y][0][0]已经预先填充
    for (int i=0;i<=log2(n);i++)
        for (int j=0;j<=log2(m);j++) {
            if (i == 0 && j == 0) continue;
            for (int x=1;x<=n;x++) for (int y=1;y<=m;y++) {
                int rangex = x + pow2(i) - 1;
                int rangey = y + pow2(j) - 1;
                if (rangex > n || rangey > m) continue;
                if (i == 0) {
                    st[x][y][i][j] = max(    st[x][        y        ][i][j-1],
                                            st[x][y+pow2(j-1)    ][i][j-1]);
                }
                else {
                    st[x][y][i][j] = max(    st[        x        ][y][i-1][j],
                                            st[x+pow2(i-1)    ][y][i-1][j]);
                }
            }
        }
}

查询

那么，同理，查询我们也可以分为4块。分别是左上，左下，右上，右下

int query_max(int x1,int y1,int x2,int y2) {
    int k1 = log2(x2-x1+1);
    int k2 = log2(y2-y1+1);
    return max(
                max(
                    st[      x1     ][y1][k1][k2],
                    st[x2-pow2(k1)+1][y1][k1][k2]
                    ),
                max(
                    st[x1][y2-pow2(k2)+1][k1][k2],
                    st[x2-pow2(k1)+1][y2-pow2(k2)+1][k1][k2]
                    )
                );
}

这里附上一道二维st表的例题和我的题解代码：

HDU 2888 Check Corners
我的题解