专栏文章

RMQ 与 LCA

wwenqinghua1001
算法·理论参与者 3已保存评论 3

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
3 条
当前快照
1 份
快照标识符
@miqi0sdg
此快照首次捕获于
2025/12/04 05:08
3 个月前
此快照最后确认于
2025/12/04 05:08
3 个月前
查看原文

RMQ 与 LCA。

树。

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

RMQ 。

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

LCA  。

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

±1RMQ 。

±1RMQ，即约束 RMQ，是特殊 RMQ，序列中两个相邻元素的差是 11 或 −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)
TarjianLCA 问题一般离线不定O(N+Q)
±1RMQ算法±1RMQ 问题一般在线O(N)O(Q)
注： NN 表示问题规模，QQ 表示询问次数。

ST 表

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

预处理

 f[i][j]f[i][j] 表示从第i个数起连续 2j2^j 个数中的最小值。
code:
CPP
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]);
}

查询

查询 ss 到 tt 这一段的最小值，先求出一个最大的 kk ，使得 kk 满足 2k<=(t−s+1)2^k<=(t-s+1) ，于是我们就可以把 [s,t][s,t] 分成 [s,s+2k−1][s,s+2^k-1]，[t−2k+1,t][t-2^k+1,t]。
code:
CPP
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:
CPP
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:
CPP
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:
CPP
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:
CPP
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:
CPP
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);
	}
}

评论

共 3 条评论，欢迎与作者交流。

正在加载评论...