二维ST表学习笔记

Table of Contents

众所周知,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]为原来的值。

这里,我用ij分别表示xy方向的范围(以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]);
  1. 对于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
我的题解

Leave a Reply

Your email address will not be published. Required fields are marked *

Back to Top