【数据结构】ST表-RMQ问题

更新于 分类于 ， 阅读次数： 本文字数： 3k 阅读时长 ≈ 3 分钟

RMQ(Range Maximum(Minimum) Query)问题，查询区间最大值或最小值，相比线段树，为静态查询，复杂度O(nlog⁡n)O(n\log n)

作用

查询区间最大值或最小值

复杂度

O(nlog⁡n)O(n\log n) 预处理，O(1)O(1) 查询

算法：倍增思想

以最大值为例，最小值取min同理

预处理

  • Max[i][j]​表示从ii 位置开始的2j2^j 个数中的最大值（最小值同理），即表示区间[i,i+2j)[ i , i+2^j ) 的最大值
  • 将[i,i+2j)[ i , i+2^j ) 区间拆成[i,i+2j−1)[ i,i+2^{j-1} )​ 和[i+2j−1,i+2j)[i+2^{j-1},i+2^j ) 两个区间，则大区间的最大值是小区间最大值的最大值
  • 更新方程：Max[i][j]=max(Max[i][j-1] , Max[i+2^{j-1}][j-1])​​ ​

查询

  • 查询[l,r][ l , r ] 区间最大值：取区间长度的对数k=log⁡2(r−l+1)k=\log_{2} (r-l+1)，查询结果为max(Max[l][k], Max[r-2^k+1][k])

  • 上述第二项r−2k+1r-2^k+1 的由来：尝试找右短点为rr 的区间。设左端点为xx ，则x+2k=r+1x+2^k =r+1（左闭右开区间），解得左端点x=r−2k+1x=r-2^k+1​

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
void init()            // 初始化，st[i][0]中记录了数组的初始值
{
    for(int j=1;j<20;j++)    // 区间长度不超过(1<<19)(524288，够用了)
        for(int i=1;i+(1<<j)-1<=n;i++)
            st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]); // 更新最大值
}
int RMQ(int l,int r)   // 查询区间[l,r]的最大值
{
    int k=log2(r-l+1); // 求左端点（算法中细说了）
    return max(st[l][k],st[r-(1<<k)+1][k]);    // 得到最大值
}
int main()             // 普通RMQ问题主函数 
{
    read(n),read(m);
    for(int i=1;i<=n;i++)
        read(st[i][0]);    // 原始值写入st[i][0]
    init();                // 初始化
    int l,r;
    for(int i=0;i<m;i++)
    {
        read(l),read(r);   // 查询
        printf("%d\n",RMQ(l,r));
    }
    return 0;
}

二维RMQ问题

目标

查询a×ba\times b 矩阵中n×nn\times n 大小的矩阵中的最大值

修改一维ST表

  • Max[i][j][k] 表示(i,j)(i,j) 为左上角，边长为2k2^k 的正方形矩阵中的最大值
  • 递推：Max[i][j][k]=max(Max[i][j][k-1], Max[i][j+2^{k-1}][k-1], Max[i+2^{k-1}][j][k-1], Max[i+2^{k-1}][j+2^{k-1}][k-1])，即将大正方形拆成上下左右四个小正方形
  • 查询：(x,y)(x,y) 为左上角，nn 为边长，k=log⁡2nk=\log_{2} n，结果为max(Max[x][y][k], Max[x][y+n-2^k+1][k], Max[x+n-2^k+1][y][k], Max[x+n-2^k+1][y+n-2^k+1][k]，区间端点的推到与一维类似
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
void init()
{
    for(int k=1;k<=(int)log2(min(a,b))+1;k++)
        for(int i=1;i+(1<<k)-1<=a;i++)
            for(int j=1;j+(1<<k)-1<=b;j++)
            {
                stmax[i][j][k]=max(stmax[i][j][k-1], max(stmax[i][j+(1<<(k-1))][k-1],
                        max(stmax[i+(1<<(k-1))][j][k-1], stmax[i+(1<<(k-1))][j+(1<<(k-1))][k-1])));
                stmin[i][j][k]=min(stmin[i][j][k-1], min(stmin[i][j+(1<<(k-1))][k-1],
                        min(stmin[i+(1<<(k-1))][j][k-1], stmin[i+(1<<(k-1))][j+(1<<(k-1))][k-1])));
            }
}
int RMQ(int x,int y)
{
    int k=log2(n+1);
    int maxn=max(stmax[x][y][k],max(stmax[x][y+n-(1<<k)][k],
                 max(stmax[x+n-(1<<k)][y][k],stmax[x+n-(1<<k)][y+n-(1<<k)][k])));
    int minn=min(stmin[x][y][k],min(stmin[x][y+n-(1<<k)][k],
                 min(stmin[x+n-(1<<k)][y][k],stmin[x+n-(1<<k)][y+n-(1<<k)][k])));
    return maxn-minn;
}
int main()
{
    read(a),read(b),read(n);
    for(int i=1;i<=a;i++)
        for(int j=1;j<=b;j++)
        {
            read(stmax[i][j][0]);
            stmin[i][j][0]=stmax[i][j][0];
        }
    init();
    int ans=inf;
    for(int i=1;i<=a-n+1;i++)
        for(int j=1;j<=b-n+1;j++)
            ans=min(ans,RMQ(i,j));
    printf("%d",ans);
    return 0;
}

其他

log也可以预处理，毕竟现在题目基本不卡常所以不重要。

1
2
3
lg[1] = 0;
for(int i = 2; i <= n; i++)
    lg[i] = lg[i / 2] + 1;

题目

Uva1618

洛谷P2216 二维RMQ

洛谷P1816

洛谷P2880