倍增lca短篇讲解（完）
2026-05-13 21:46:50
发布于：上海
为次小生成树准备的一篇。重点会放在树上倍增。
题目的题意还是相当明确的。
图示：
图中AB两点的最近公共祖先就是那个红点点。
如何求取最近公共祖先：
已知有两个点A和B。
1.将A和B提高到同一个高度
2.它们一起往上跳。直到跳到最近公共祖先。
不难发现这两个操作都可以靠着暴力模拟完成。不难发现这样立马就会TLE。
这里我们的解决方案有很多种，不过这篇帖子选择介绍倍增的方案。
接下来我会一边讲述代码框架一边讲解倍增。
1.初始化
vector<int>v[N];
int deep[N],f[N][30];
void dfs(int x,int pos){
f[x][0]=pos;
deep[x]=deep[pos]+1;
for(int i=1;(1<<i)<=n;i++){
f[x][i]=f[f[x][i-1]][i-1];
}
for(int i=0;i<v[x].size();i++){
if(v[x][i]==pos)continue;
dfs(v[x][i],x);
}
}
关于倍增
顾名思义”成倍增长“。一般默认是二次幂成倍增长。
它可以把时间复杂度为的暴力枚举优化成。
这之中的核心诀窍就是：一个数可以有一堆二的次幂拼凑而成。
这个说法的最直观的体现是二进制。
接下来我们会逐渐感受到倍增的魅力。
和的含义：是当前节点，是节点的父亲节点。
数组的含义：f[i][j]表示第i个点网上爬个点后到达的祖先节点。
这个公式是根据数学结论推导出来的。
因为： 所以就有了上面的那行代码。
在根据这行代码更新之前，我们需要把所有的更新好。
所以循环从小到大遍历。
数组的含义：顾名思义，它记录每个结点的深度。
的意思是：当前节点的深度=其父节点的深度+1
2.将和两个点升到同一高度
if(deep[a]<deep[b])swap(a,b);
int len=deep[a]-deep[b];
for(int i=19;i>=0;i--){
if(len>>i&1)a=f[a][i];
}
if(a==b)return a;
首先，我们打算将a往上拎，所以肯定要确保。
把a往上拎的过程需要用到倍增的思想，具体原理前面已经解释过了。（for循环从小到大遍历还是从大到小遍历都可以）
然后这时候如果与相等，那么证明当前已经到达最近公共祖先了，可以（其实是必须，要不然后面就会出问题）直接返回。
3.点和点一起往上跳到最近公共祖先（这一段也是我不太确定的，如果有疑问和质疑欢迎私信我or直接在评论区提出。评论我都会看的，感谢。）
for(int i=19;i>=0;i--){
if(f[a][i]==f[b][i])continue;
a=f[a][i];
b=f[b][i];
}
return f[a][0];
接下来就是一步步往上跳。
if(f[a][i]==f[b][i])continue;
这句判断还是很有意思的。
如果点往上跳到达的顶点和点往上跳步到达的顶点是相同的就跳过。
可能会有人认为：如果相同那不就代表是最近公共祖先了？直接return不好吗。
它确实是公共祖先，但不一定是最近，看这幅图：
现在点往上跳个点到达了绿点。绿点确实是公共祖先，但并不是最近。
就算真的是红点。
所以说最后是：
return f[a][0];
而不是：
return a;
另：关于为什么是从大到小枚举i而不是从小到大枚举？
由于需要加的距离实际上是固定的，我们先加大的，就可以用小的补（每个都只能加一次）。
就像是往一个箱子里面装海绵。
前面你不管用大海绵还是小海绵装，最后你的箱子里面总归还是有缝隙。
如果你先用大海绵，你后面就可以用没用的小海绵来填充缝隙。
但是如果你先用小海绵，你后面想填充缝隙时，就会发现大海绵无法使用。
有帮助，赞一个