RMQ 问题的两种实现办法（线段树查询和稀疏表(Sparse Table表)查询）

引言

RMQ算法(Range Minimum/Maximum Query) 是静态区间极值查询的高效算法，在各种算法竞赛中常常出现，虽然不会单独拿出来做一个题，但是经常作为题的一部分。依据所需实现的不同性能可以有多种写法,这里主要讲基于线段树和稀疏表(Sparse Table)的两种方法。

线段树实现RMQ

线段树是维护区间的一类高效数据结构,依据这个特性,我们可以用线段树实现RMQ算法,用线段树实现的RMQ算法不仅可以查询区间最小值,还可以更改某个节点的值。

时间复杂度：预处理时O（nlogn），单次询问O（longn）

void Build(int p,int l,int r)
{
    if(l == r)
    {
        tree[p] = x[l];
        return;
    }
    int mid = (l + r) / 2;
    Build(p * 2,l,mid);
    Build(p * 2 + 1,mid + 1,r);
    tree[p] = min(tree[p * 2],tree[p * 2 + 1]);
}
int Query(int p,int l,int r,int x,int y)
{
    /*在plr这棵子树里查询x到y区间的最小值*/
    if(x <= l && r <= y)
        return tree[p];
    int mid = (l + r) / 2;
    if(y <= mid)
        return Query(p * 2,l,mid,x,y);
    if(x > mid)
        return Query(p * 2 + 1,mid + 1,r,x,y);
    return min(Query(p * 2,l,mid,x,mid),Query(p * 2 + 1,mid + 1,r,mid + 1,y));
}

ST表实现RMQ

线段树的查询复杂度为O(log n),对于有多组询问的题还是太慢,有了线段树实现的铺垫,我们思考,是否有一种方法能预先处理出区间极值呢,答案是有的,就是ST表。

时间复杂度：预处理时O（nlogn），单次询问O（1）

预处理的时候用到一种dp的思想。

d[i][j]代表这样一段区间的最值：左端点为i，长度为2^j，也就意味着它管辖了[i,i + 2 ^(j - 1)]。

void st_init(int n)
{
    for(int i = 1;i <= n; i++)
        d[i][0] = x[i];
    for(int j = 1;(1 << j) <= n; j++)
        for(int i = 1;i + (1 << j) - 1 <= n; i++)
            d[i][j] = min(d[i][j - 1],d[i + (1 << (j - 1))][j - 1]);
    for(int i = 1;i <= n; i++)
    {
        int k = 0;
        while((1 << (k + 1)) <= i)
            k++;
        mn[i] = k;
    }
}
int STquery(int l,int r)
{
    int k = mn[r - l + 1];
    return min(d[l][k],d[r - (1 << k) + 1][k]);
}