关于
联系
Oi大佬们
keyboard_arrow_down
本站已运行
载入天数...载入时分秒...
Woshiluo's Notebook
Woshiluo
2018年6月2日
科学解决 RMQ 问题 — 线段树/(ST/稀疏表)/分块

RBQRMQ

区间最值问题

大概就是那种给你一串数字,然后问你在区间[l,r]内,求最小值或最大值

一般,我们的操作,就是暴力枚举 然后你就光荣的TLE/MLE

然后让我们来说说区间问题的三种解法—线段树/ST表与分块

线段树


预处理: O( n*log(n) )
查询: O( log(n) )
单点更新: 支持,不破坏查询复杂度

写的爽,调的更爽

线段树是一种数据结构 首先我们需要了解一种东西,哈弗曼树 显然,对于一颗二叉树,如果一个节点号为n那么它的左节点是2n,右节点是2n+1 然后我们就可以愉快的存树了 然后什么是线段树呢? 吃的 它是能够维护一定区间的树 他的根节点是[L,R](最左和最右)的最优值 然后左节点是[L,(L+R)/2]的最优值 右节点是[(L+R)/2+1,R]的最优值 往后以此类推 直到l==r为止 简单代码如下:

这个代码对应[https://www.luogu.org/problemnew/show/P4644]这道题

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int n,m,e;
struct whi{
    int left,rig,cost;
}a[11000];
int f[110000];
int tree[11000000];

bool cmp(whi a,whi b){
    return a.rig<b.rig;
}
// 创建
void build(int p,int l,int r){// p 当前下标 l 左端点 r 右端点
    if(l==r) {tree[p]=f[l];return ;}
    build(p<<1,l,(l+r)>>1);
    build(p<<1|1,((l+r)>>1)+1,r);
    tree[p]=min(tree[p<<1],tree[p<<1|1]);
}
// 更新单点
void update(int p,int l,int r,int now,int val){// p 当前下表 l 当前左端点 r 当前右端点 now 当前点的边界 val 更新的值 
    if(l==r&&l==now){tree[p]=val;return ;}
    if(now<=((l+r)>>1)) update(p<<1,l,(l+r)>>1,now,val);
    else update(p<<1|1,((l+r)>>1)+1,r,now,val); 
    tree[p]=min(tree[p<<1],tree[p<<1|1]);
}
// 求区间最值
int query(int p,int l,int r,int ll,int rr){//p 当前下表  l 当前左端点 r 当前右端点 ll 需求左端点 rr 需求右端点
    if(ll<=l&&rr>=r){return tree[p];}
    int ans=0x7fffffff,mid=(l+r)>>1;
    if(ll<=mid) ans=min(ans,query(p<<1,l,mid,ll,rr));
    if(rr>mid) ans=min(ans,query(p<<1|1,mid+1,r,ll,rr));
    return ans;
} 

int main(){
    memset(f,0x3f,sizeof(f));
    scanf("%d%d%d",&n,&m,&e);
    m++;e++;
    for(int i=1;i<=n;i++){
        scanf("%d%d%d",&a[i].left,&a[i].rig,&a[i].cost);
        a[i].left++;a[i].rig++;
    }
    sort(a+1,a+n+1,cmp);
    /*for(int i=1;i<=n;i++){
        printf("%d %d %d\n",a[i].left,a[i].rig,a[i].cost);
    }*/
    f[m-1]=0;
    build(1,m-1,e);
    for(int i=1;i<=n;i++){
        if(a[i].rig<m) continue;
        if(a[i].left<=m) f[a[i].rig]=min(f[a[i].rig],a[i].cost);
        else f[a[i].rig]=min(f[a[i].rig],query(1,m-1,e,a[i].left-1,a[i].rig)+a[i].cost);
        update(1,m-1,e,a[i].rig,f[a[i].rig]);
    }
    if(f[e]>=1061109567) printf("-1");
    else printf("%d",f[e]);
}

当然这个并不是线段树的完整用法wq 更详细的用法,请看下篇题解

ST/稀疏表

> 速度虽快,更新却难

预处理: O( n*log(n) )
查询: O( 1 )
单点更新: 支持,需重新预处理

ST/稀疏表(以下统称)ST表,是一种基于倍增思想的玄学算法 比如说我们用f[i][j]储存从 i 位置开始的 2^j个数中的最大值 那么转移的时候我们可以把当前区间拆成两个区间并分别取最大值 查询先计算出 log2(区间长度) 然后对于左端点和右端点分别进行查询,这样可以保证一定可以覆盖查询的区间 然后你就会发现一堆log和换底公式出现于你的程序中 感性理解吧~ 但是不难理解

对应例题:[https://www.luogu.org/problemnew/show/P3865]

#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;

int n,m,l,r;
int a[110000];
int f[110000][110];

int st_query(int l,int r){
    int k=log(r-l+1)/log(2);
    return max(f[l][k],f[r-(1<<k)+1][k]);
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        f[i][0]=a[i]; 
    }

    int t=log(n)/log(2)+1;
    for(int j=1;j<t;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]);
        }
    }

    for(int i=1;i<=m;i++){
        scanf("%d%d",&l,&r);
        printf("%d\n",st_query(l,r));
    }
}

看起来是不是相当简单qwq 但是要千万注意log时该加1时不该加时不加1

分块


高端的模拟

预处理: O(n)
查询: O(sqrt(n))
更新: O(sqrt(n))

先说说什么是分块算法吧

分块,顾名思义,就是将一个数列分成几块单独处理,比如讲[1,5]分成三块就是[1,2] [3,4] [5]这三个

那么我们查找[1,3]的最小值,只需要查找第一个与第二个块的最小值

经过一些证明,我们可以知道,在分成sqrt(n)块的情况下最优

所以就有了复杂度中的一堆sqrt(n)

那么代码我相信大家心里都有数了 那么和线段树一样,代码下篇题解讲,毕竟都是一道题目嘛wq

End


这几种解法,只是一种板子,而真正的RMQ算法,可能会结合多种东西,或者被多种东西所结合,所以说活学活用是最重要的,无论如何,刷题是最重要的

“Happy Coding Life”