ST表解决RMQ问题


ST表解决RMQ问题


RMQ问题

    RMQ问题是指 求给定区间内的最大(最小)值 问题,如下:

给定 n 个数,有 m 个询问,对于每个询问,你需要回答区间 [l, r] 中的最大值。

解决这类问题的方法有很多,这里要说的就是我最近学习到的ST表


ST表

    ST表基于序列上的倍增的思想,能够在O(nlogn)内预处理,O(1)的时间复杂度在线回答区间[l, r]中的最大(最小)值。

那么为什么要用倍增的思想呢? 当然是为了减小时间复杂度,在ST表模板中,主要是对一个二维数组f进行预处理操作,让fi表示数列中在[i, i + $$2^j$$ - 1]区间的最大(最小)值。

那么为什么不让fi直接表示数列中在[i, j]的最大(最小)值呢?这样表示的话回答的时间复杂度也是O(1)啊? 那是为了减小空间复杂度(从O($$n^2$$)降到了O(nlogn)),从而也就减小时间复杂度(处理的数据减小)。并且这样做回答的时间复杂度没变啊,还是O(1),多好。

那既然你可以在O(1)的时间回答给定区间[l, r],你怎么保证[l, l + $$2^j$$ - 1]能够表示区间[l, r]呢?l + $$2^j$$ - 1 直接等于 r 不一定能做的到,但是我们可以先计算出k = $$\log_{2}{(r - l + 1)}$$ .这个k满足$$2^k <= r - l + 1$$.然后用区间[l, l + $$2^k$$ - 1]和区间[r - $$2^k$$ + 1, r] (这两个区间对应f数组分别为 f [l] [k] 和 f [r - $$2^k$$ + 1] [k] ) 中的最大值来回答提问的区间[l, r].即使这两个区间重叠了也没有关系,只要这两个区间完整的覆盖到[l, r]区间,即可.

那么这个二维数组 f 到底怎么进行预处理呢 ? f [i] [j]表示区间是[i, i + $$2^j$$ - 1], 这个区间分成左右两半就是f [i] [j - 1]和f [i + $$2^{j - 1}$$] [j - 1],那么递推关系就是f [i] [j] = max(f [i] [j - 1], f [i + $$2^{j - 1}$$] [j - 1]).而f [i] [0]则是边界,f [i] [0] = a [i], 数组 a ,表示数列A.


模板

    我结合了一下OI Wiki《算法竞赛进阶指南》 上的模板, 如下:

const int MAX = 50000;
int f[MAX][17], Logn[MAX];
void ST_prework()
{
    Logn[1] = 0;
    Logn[2] = 1;
    for(int i = 3; i <= n; i++)
        Logn[i] = Logn[i >> 1] + 1;
    for(int i = 1; i <= n; i++)
        f[i][0] = a[i];
    for(int j = 1; j <= Logn[n]; j++)
        for(int i = 1; i <= n - (1 << j) + 1; i++)
            f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
}
int ST_query(int l, int r)
{
    int k = Logn[r - l + 1];
    return max(f[l][k], f[r - (1 << k) + 1][k]);
}

例题

题目传送点这里 poj2019

题目大致意思就是给你一个矩阵数组, 随机问你矩阵中以某一点为左上角构成 B * B 大小的子矩阵中的最大值与最小值的差值.具体请看原题

题解:

开始我百度了一下找到了一个二维RMQ的模板,改了一下,就可以用了.如下:

#include <stdio.h>
#include <algorithm>
using namespace std;
const int MAX = 255;
int f[MAX][MAX][17][17], g[MAX][MAX][17][17], val[MAX][MAX];
int RMQ_MAX(int x1, int y1, int x2, int y2)
{
    int kx = 0, ky = 0;
    while((1 << (1 + kx)) <= x2 - x1 + 1)   kx++;
    while((1 << (1 + ky)) <= y2 - y1 + 1)   ky++;
    int m1 = f[x1][y1][kx][ky];
    int m2 = f[x2 - (1 << kx) + 1][y1][kx][ky];
    int m3 = f[x1][y2 - (1 << ky) + 1][kx][ky];
    int m4 = f[x2 - (1 << kx) + 1][y2 - (1 << ky) + 1][kx][ky];
    return max(max(m1, m2), max(m3, m4));
}
int RMQ_MIN(int x1, int y1, int x2, int y2)
{
    int kx = 0, ky = 0;
    while((1 << (1 + kx)) <= x2 - x1 + 1)   kx++;
    while((1 << (1 + ky)) <= y2 - y1 + 1)   ky++;
    int m1 = g[x1][y1][kx][ky];
    int m2 = g[x2 - (1 << kx) + 1][y1][kx][ky];
    int m3 = g[x1][y2 - (1 << ky) + 1][kx][ky];
    int m4 = g[x2 - (1 << kx) + 1][y2 - (1 << ky) + 1][kx][ky];
    return min(min(m1, m2), min(m3, m4));
}
int main()
{
    int n, b, k;
    scanf("%d%d%d", &n, &b, &k);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
        {
            scanf("%d", &val[i][j]);
            f[i][j][0][0] = g[i][j][0][0] = val[i][j];
        }
    for(int i = 0; (1 << i) <= n; i++)
        for(int j = 0; (1 << j) <= n; j++)
        {
            if(i == 0 && j == 0)    continue;
            for(int row = 1; row + (1 << j) - 1 <= n; row++)
                for(int col = 1; col + (1 << j) - 1 <= n; col++)
                {
                    if(j == 0){
                        f[row][col][i][j] = max(f[row][col][i - 1][j], f[row + (1 << (i - 1))][col][i - 1][j]);
                        g[row][col][i][j] = min(g[row][col][i - 1][j], g[row + (1 << (i - 1))][col][i - 1][j]);
                    }
                    else{
                        f[row][col][i][j] = max(f[row][col][i][j - 1], f[row][col + (1 << (j - 1))][i][j - 1]);
                        g[row][col][i][j] = min(g[row][col][i][j - 1], g[row][col + (1 << (j - 1))][i][j - 1]);
                    }
                }
        }
    int x, y;
    while(k--)
    {
        scanf("%d%d", &x, &y);
        printf("%d\n", RMQ_MAX(x, y, x + b - 1, y + b - 1) - RMQ_MIN(x, y, x + b - 1, y + b - 1));
    }
    return 0;
}

可惜的是内存超限了...

我想了想可以把二维矩阵压缩成一维数组,然后套ST表的模板.如下为AC代码:

#include <stdio.h>
#include <algorithm>
#include <math.h>
using namespace std;
const int MAX = 62505;
int f[MAX][17], g[MAX][17], Logn[MAX];
int ST_queryMin(int l, int r)
{
    int k = Logn[r - l + 1];
    return min(g[l][k], g[r - (1 << k) + 1][k]);
}
int ST_queryMax(int l, int r)
{
    int k = Logn[r - l + 1];
    return max(f[l][k], f[r - (1 << k) + 1][k]);
}
int main()
{
    int n, b, k;
    scanf("%d%d%d", &n, &b, &k);
    int n2 = n * n;
    Logn[1] = 0;
    Logn[2] = 1;
    for(int i = 3; i <= n2; i++)
        Logn[i] = Logn[i >> 1] + 1;
    for(int i = 1; i <= n2; i++)
    {
        scanf("%d", &f[i][0]);
        g[i][0] = f[i][0];
    }
    for(int j = 1; j <= Logn[n2]; j++)
        for(int i = 1; i <= n2 - (1 << j) + 1; i++)
        {
            f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
            g[i][j] = min(g[i][j - 1], g[i + (1 << (j - 1))][j - 1]);
        }
    int x, y, minv, maxv;
    while(k--)
    {
        scanf("%d%d", &x, &y);
        minv = 0x7fffffff, maxv = 0;
        for(int i = x; i < x + b; i++)
        {
            maxv = max(maxv, ST_queryMax((i - 1) * n + y, (i - 1) * n + y + b - 1));
            minv = min(minv, ST_queryMin((i - 1) * n + y, (i - 1) * n + y + b - 1));
        }
        printf("%d\n", maxv - minv);
    }
    return 0;
}

用时400+ms...
其实这题数据是可以暴力卡过的,如下为暴力ac的,用时1000ms...笑死我了:

//暴力 时间卡的死死的给了1000ms我就用了1000ms
// accepted
#include <stdio.h>
const int SIZE = 255;
int matrix[SIZE][SIZE];
int main()
{
    int n, b, k;
    scanf("%d%d%d", &n, &b, &k);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            scanf("%d", &matrix[i][j]);
    int x, y;
    while(k--)
    {
        scanf("%d%d", &x, &y);
        int min = matrix[x][y], max = matrix[x][y];
        for(int i = x; i < x + b; i++)
            for(int j = y; j < y + b; j++)
            {
                max = (max < matrix[i][j]? matrix[i][j]: max);
                min = (min < matrix[i][j]? min: matrix[i][j]);
            }
        printf("%d\n", max - min);
    }
    return 0;
}

不过这样没什么意义,这次能卡过,下次就可以卡哭...还是学习知识才是首要目的.

声明:Trikker的小破站|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - ST表解决RMQ问题


分享一些学习成果