LCA(总结+模板)


LCA介绍

LCA即最近公共祖先问题,求一棵树上两个点的最近祖先。

LCA有两种类型的算法,离线算法和在线算法

  • 离线算法

    1. Tarjan算法
  • 在线算法
    1. 倍增算法
    2. LCA转化RMQ

LCA算法介绍

Tarjan算法

Tarjan算法是离线算法,时间复杂度$O(n+q)$,主要是dfs和并查集

  先来个树




  这个算法主要就是dfs搜索时每次都行搜子树,然后用并查集把子节点跟父节点连到一起,因为是深搜(假设搜a-b)

  1. 查询两个点在同一支上,那么在上面的点就是最近祖先,在搜到子树点时都会用并查集跟父节点压缩到一块,直到最后到的点(a),最后查询到find(b)(假设a在上)而find(b)因为路上的节点压缩等于a
  2. 查询的两个点不在同一支上,那么最近祖先就是这个子树的根节点,和1一样(假设先搜到b)它也是一直压缩到它的父节点在换右支时,find(b)就是这颗子树的根节点,最后查询到find(b)(假设a在上)而find(b)因为路上的节点压缩等于a
  3. 在说一个例子吧.
    假设看这个图中的一颗小树 8 4 6 15 7 然后查 15-7 15-4 7-4 ,我们来模拟一下,直接搜到最底层 15 没有子树,把15和他的父节点连到一块,标记15号点,然后找所有与15有关的查询 ,有两个15-7 15-4,然后发现4 7都没有标记,不处理回退到6 ,然后进到7,和15一样操作,在查找与7相关的查询是发现15已经标记过了,这时候find(15)就是 15-7的最近祖先,其他点也类似
  4. 代码(模板)
    1
    待补充
倍增算法

一种很神奇的算法,与RMQ原理相似,都是利用打表,时间复杂度$O((n+q)logn)$

同样先来个树




  倍增,一种好的思想,可惜我还是不懂qaq ,这个原理容易懂,先跑出来距离每个点距离为1的祖先节点,这个很容易找,就是一遍dfs的事,然后利用倍增的思想,递推出所有距离该节点二的次方的所有节点,例如f[i][j]=f[f[i][j-1]][j-1] (i代表节点 j代表距离$2^j$ ,就是距离一个节点$2^n$等于距离<距离这个节点$2^{n-1}$的节点>的节点$2^{n-1}$的节点),这个算法就是在你打完所有距离每一个节点2的次幂距离的点的表后,去处理

  1. 先把两个节点调到一个高度,把一个节点往上移动 a=f[a][j],移动多少呢,因为我们存下的都是二的倍数,所以你会想到二进制,直接把两个数高度差的二进制移动
  2. 到同一高度后,同时往上移动,一个一个移动肯定很慢啊,怎么办呢还是利用二进制啊,倍增好像就是这样,用二的次幂处理,我们可以倒着尝试移动,从直接移动
  3. log2(n)(why? log2(n)就是移动$2^{log_2(n)}$次肯定会移动到最上面滴)如果相等,那就是在移动$2^{log_2(n)}$之前就有可能找到一个相同点,那么这个就不移动,继续找,最后这个点的父节点就是最近公共祖先
  4. 例子就没必要了,自己推吧
  5. 代码
    1
    待补充
LCA 转化成RMQ
RMQ 算法介绍

就是求一段数列的最大值,和最小值 预处理$nlog(n)$ 查询 $O(1)$

  RMQ也是利用的倍增的思想,陷于处理出从i点开始2的次幂个数的最小值,然后进行查询,如何做呢,首先求出2的0次幂(也就是它本身),然后同样递推dp[i][j]=min(dp[i][j-1],dp[i+(1<<j)][j-1]) (dp[i][j]是 从第i未开始 $2^j$个数的最小值),这样就可以求出来了,如何查询呢?就是把这个区间分成两块,然后合在一起,假设查询区间[l,r],那么我们只需要找两个区间 ,首先找一个k 代表从i开始k个数,这个k要尽可能的大,其实也就是$log_2(r-l+1)$这时候区间可写成[l , l+$2^k$][r-($1<<k$)+1,r]区间的并集,也就是这两个区间的最小值

代码

1
待补充

LCA转化RMQ方法

  这个方法的原理我还是不懂,只知道两个都是倍增,中间有一定的关系

  先看个图




  欧拉序列,很容易看出来是什么,就是遍历这棵树所走的顺序
  深度序列,从名字上就知道是什么了,这里是与欧拉序列相对应点的深度
  frist,第一次经过该点时的所在欧拉序列中的位置

  这有什么用呢?我们来查找一下试试例如找 5-4,首先我们先找frist(5)和frist(4)找到在欧拉序列中的位置,看这个区间的深度序列,你会发现这个区间最小的值所在位置就是这两个点的最近祖先,找最小的位置那当然是用新学的rmq啦

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cmath>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;
#define ll long long
#define rd(a) scanf("%d",&a)
#define rld(a) scanf("%lld",&a)
#define rs(a) scanf("%s",a)
#define me(a,b) memset(a,b,sizeof(a))
#define pb(a) push_back(a)
const ll maxn=5e4+10;
const ll mod =1e9+7;
const ll inf =0x3f3f3f3f;
const double PI=acos(-1);
bool vis[maxn];
vector<pair<int,int>>q[maxn]; //存图
int df[maxn*2]; //深度序列
int tp[maxn*2]; //拓扑序列
int frist[maxn]; //第一次出现的位置
int cnt=0; //序列计数
int d[maxn];//求距离
void dfs(int u,int dh){ // 找 df tp frist d

vis[u]=true;
tp[cnt]=u;
df[cnt]=dh;
frist[u]=cnt;
cnt++;
for(int i=0;i<q[u].size();i++){

int v=q[u][i].first;
int dis=q[u][i].second;
if(vis[v]) continue;
d[v]=d[u]+dis;
dfs(v,dh+1);
tp[cnt]=u;
df[cnt]=dh;
cnt++;
}



}
int dp[maxn*2][30];
void get_ST(){ //rmq 打标

for(int i=0;i<cnt;i++)
{
dp[i][0]=i;
}
for(int i=1;(1<<i)<cnt;i++){
for(int j=0;j+(1<<i)-1<cnt;j++){
int a=dp[j][i-1];
int b=dp[j+(1<<(i-1))][i-1];
if(df[a]<=df[b]){
dp[j][i]=a;
}
else dp[j][i]=b;
}

}

}
int rmq(int l,int r){ //rmq 查询
if(l>r) swap(l,r);
int k=0;
while((1<<(k+1))<=r-l+1) k++;
if(df[dp[l][k]]<=df[dp[r-(1<<k)+1][k]]) return dp[l][k];
else return dp[r-(1<<k)+1][k];


}
int lca(int a,int b){ //lca 查询
a=frist[a];
b=frist[b];
return tp[rmq(a,b)];


}
void init(){ //初始化
me(vis,0);
me(d,0);
cnt=0;

}

入门题

题目题解
POJ-1330暂无
HDU-2586暂无
如果对您有帮助,请小小支持一下,您的支持将鼓励我继续创作!
0%