RMQ 与 LCA

· · 算法·理论

RMQ 与 LCA。

树。

【关键词】

RMQ，LCA，ST 算法，Tarjian 离线算法，±1RMQ，笛卡尔树，欧拉序列，并查集。

RMQ 。

RMQ（Range Minimum/Maximum Query），即区间最值问题。

LCA  。

LCA（Lowest Common Ancestor），即最近公共祖先。

±1RMQ 。

±1RMQ，即约束 RMQ，是特殊 RMQ，序列中两个相邻元素的差是 1 或 -1 。

算法名称 针对问题 难度 在/离线 预处理时间 Q次询问时间
ST 表 一般  RMQ 问题 容易 在线 O(N*logN) O(Q)
分块 动态 RMQ 问题 容易 在线 O(N) O(Q*平方根(N))
线段树 动态 RMQ 问题 较难 在线 O(N) O(Q*logN)
树上倍增 LCA 问题 较难 在线 O(N*logN) O(Q*logN)
Tarjian LCA 问题 一般 离线 不定 O(N+Q)
±1RMQ算法 ±1RMQ 问题 一般 在线 O(N) O(Q)

注： N 表示问题规模，Q 表示询问次数。

ST 表

ST 算法（Sparse Table），分为预处理和查询两部分。

预处理

 f[i][j] 表示从第i个数起连续 2^j 个数中的最小值。

code:

int minST[MAXN][20];
void InitMinST(int a[], int n){
    for(int i=0;i<=n;i++)
        minST[i][0]=a[i];
    for(int j=1;(1<<j)-1<=n;j++)
        for(int i=0;i+(1<<j)-1<=n;i++)
            minST[i][j]=min(minST[i][j-1],minST[i+(1<<(j-1))][j-1]);
}

查询

查询 s 到 t 这一段的最小值，先求出一个最大的 k ，使得 k 满足 2^k<=(t-s+1) ，于是我们就可以把 [s,t] 分成 [s,s+2^k-1]，[t-2^k+1,t]。

code:

int RMQMIN(int s,int t){
    int k=(int)(log2(t-s+1.0));
    return min(minST[s][k],minST[t-(1<<k)+1][k]);
}

树上倍增 LCA。

如何倍增求LCA。

预处理

code:

int dep[MAXN],fa[MAXN][20];
int q[MAXN],f,r;
void InitLCA(int rt){
    int u,v;
    f=r=0;
    memset(fa,-1,sizeof(fa));
    dep[rt]=1;
    q[r++]=rt;
    while(f<r){
        u=q[f++];
        for(int i=h[u];i>0;i=e[i].p){
            v=e[i].v;
            if(v==fa[u][0])
                continue;
            fa[v][0]=u;
            dep[v]=dep[u]+1;
            for(int j=1;j<20;j++){
                if(fa[v][j-1]!=-1)
                    fa[v][j]=fa[fa[v][j-1]][j-1];
                else
                    break;
            }
            q[r++]=v;
        }
    } 
}
查询

code:

int QLCA(int u,int v){
    if(dep[u]<dep[v]) swap(u,v);
    int delta=dep[u]-dep[v];
    for(int i=0;i<20;i++){
        if((1<<i)&delta)
            u=fa[u][i];
    }
    if(u==v) return v;
    for(int i=19;i>=0;i--){
        if(fa[u][i]!=fa[v][i]){
            u=fa[u][i];
            v=fa[v][i];
        }
    }
    return fa[u][0];
}

Tar jan 求 LCA。

在DFS时，并查集维护了这样一些集合，集合内的所有节点与当前节点的LCA都是集合的代表元（也是集合中所有节点在原树上的根节点）。

并查集。

Tarjan中的并查集需要注意一点细节，即合并时代表元必须是当前子树的父亲节点。

code:

int f[MAXN];
void InitBCJ(int n){
    for(int i=0;i<=n;i++)
        f[i]=i;
} 
int Find(int x){
    return x==f[x]?x:f[x]=Find(f[x]);
}
int Union(int x,int y){// 注意将y合并到x 。
    int a=Find(x),b=Find(y);
    if(a==b)
        return a;
    else
        return f[b]=a;
}

询问前向星。

code:

int qh[MAXN],qcnt;
struct Query{
    int v;
    int p;
    int num;
}q[MAXN<<1];
void AddQuery(int u,int v,int num){
    q[++qcnt].v=v;
    q[qcnt].num=num;
    q[qcnt].p=qh[u];
    qh[u]=qcnt;
}

Tar jan_DFS 。

code:

int vis[MAXN],lca[MAXN];
void InitLCA(int n){
    qcnt=0;
    InitBCJ(n);
    memset(lca,-1,sizeof(lca));
}
void Tarjan(int u,int fa){
    vis[u]=1;
    int v;
    for(int i=qh[u];i>0;i=q[i].p){
        if(vis[q[i].v])
            lca[q[i].num]=Find(q[i].v);
    }
    for(int i=h[u];i>0;i=e[i].p){
        v=e[i].v;
        if(v==fa)
            continue;
        Tarjan(v,u);
        Union(u,v);
    }
}