RMQ 与 LCA

· · 算法·理论

LCA：

即是给定一个有根树 T ，对于两个节点 u，v，找到一个离根最远的结点 x，使 x 同时是 u，v 的祖先，x 便是 u，v 的最近公共祖先。

±1RMQ：

即约束 RMQ，是 RMQ 的一个特殊情况，特殊性在于：序列中每两个相邻元素的差是 1 或 -1。

小结：

算法名 问题 难度 是否在线 预处理时间 Q次询问时间
ST表 RMQ 容易 是 O(N * logN) O(Q)
分块 动态RMQ 容易 是 O(N) O(Q * \sqrt N)
线段树 动态RMQ 较难 是 O(N) O(Q * \sqrt N)
树上倍增 LCA 较易 是 O(N * logN) O(Q * logN)
Tarjan LCA 一般 否 \ O(N+Q)
±1RMQ ±1RMQ 一般 是 O(N) O(Q)

ST表 RMQ：

预处理：f(i,j) 表示 [i,i+2^j-1] 区间中的最小值，即 f[i,j] 表示从第 i 个数起连续 2^j个数中的最小值。

f(i,j)=min(f(i,j-1),f(i+ 2^{(j-1)}),j-1))

RMQ代码：

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)<=n;j++)
        for (int i=0;i+(1<<j)-1<=n;i++)
            minST[i][j]=min(minST[i][j],minST[i+(1<<(j-1))][j-1]);
}

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代码：

int dep[MAXN],fa[MAXN][20];
int q[MAXN],f,r;
void InitLCA(int rt){
    iny 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;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;
        }
    }
}
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];
}

Tarjan求LCA代码：

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){
    int a=Find(x),b=Find(y);
    if (a==b) return a;
    return f[b]=a;
}
int qh[MAXN],qcnt;
struct Query{
    int v,p,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;
}
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;i=q[i].p)
        if (vis[q[i].v]) lca[q[i].num]=Find(q[i],v);
    for (int i=h[u];i;i=e[i].p){
        v=e[i].v;
        if (v==fa) continue;
        Tarjan(v,u);
        Union(u,v);
    }
}