算法学习笔记(5): 最近公共祖先(LCA)

算法,学习,笔记,最近,公共,祖先,lca · 浏览次数 : 243

小编点评

**算法学习笔记(3): 倍增与ST算法复杂度分析** **树链剖分** * 重链:指每一条重链中最顶端的结点 * 重边:指两条重链中最顶端的结点之间连接的结点 * 重链的求和:从上到下跳至同一条链上的所有结点 **ST表** * ST表:指用以维护树上信息的数组 * ST表的初始化: * dfn[x] = dep[par] + 1, fa[x] = par * siz[x] = 1 * for all y, edge[i].to = y dep[x] += 1 fa[x] = par siz[x] += siz[y] if (siz[y] >= siz[son[x]]) son[x] = y **work**函数 * 用于求树链剖分中每个结点的深度 * 用深度来更新其他结点的父节点深度和子节点深度 * 在同一条链上跳至不同结点的深度 ****top**函数 * 用于求树链剖分中每个结点的父节点深度和子节点深度 * 用深度来更新其他结点的父节点深度和子节点深度 * 在同一条链上跳至不同结点的深度 ****lca**函数 * 用于求树链剖分中任意两个结点的最近共同祖先 * 用深度来更新其他结点的父节点深度和子节点深度 * 在同一条链上跳至不同结点的深度

正文

最近公共祖先(LCA)

最近公共祖先是树上的概念,不了解树的出门左转百度:树(数据结构名词)_百度百科

定义

假设我们需要求 xy 的最近公共祖先,这里有多种等价的定义

  • 路径 xy 上深度最小的点

  • xy 公共祖先中深度最大的点

  • xy 在这棵树上距离最近的公共祖先结点

如果 x 就是 y 的祖先,则 x 本身就是两者的最近公共祖先

求法

通常来说有四种

  • 树上倍增

  • dfs序与ST表

  • 树链剖分

  • Tarjan (离线算法)

这里我们只讨论前三种在线算法

方法一:树上倍增

倍增的思想可以看一下这篇文章:算法学习笔记(3): 倍增与ST算法

这是基于朴素方法的优化,所以在讲树上倍增之前我们还需要讲一下朴素的方法


朴素算法

选择 xy 中深度较大的点,向上跳直到两者深度相同,然后两者同时向上跳直到两者第一次相遇,此时两者所在即是最近公共祖先


显然,我们每次只跳一个显然不优,所以借鉴倍增与二进制拆分的思想

fa[x][k] 指从 x 开始,向上跳 2^k 次所能达到的祖先,特别的,如果深度不够,则 fa[x][k] = 0

那么,基于朴素算法的流程:我们只需要跳的时候利用倍增的思想就行了

这里给出一种参考代码:

notice: 这其实不是一种特别好的写法

int lca(int x, int y) {
    int p;
    // 这里保证了x是深度相对较大那一个
    if (dep[x] < dep[y]) p = x, x = y, y = p;

    // 将x跳到与y深度相同的位置
    p = 0;
    while (p >= 0) {
        if (dep[fa[x][p]] >= dep[y]) x = fa[x][p], ++p;
        else --p;
    }

    // 达到同样深度就已经相遇(y是x的祖先)
    if (x == y) return x;

    // 两者同时向上跳直到相遇
    p = 0;
    while (p >= 0) {
        if (fa[x][p] != fa[y][p]) x = fa[x][p], y = fa[y][p], ++p;
        else --p;
    }
    // 最后还要向上跳一个才是公共祖先
    // 通过这种倍增写法得出的位置是最后一个满足if条件的位置!!!
    return fa[x][0];
}

Update At 2023.06.29:有更好的写法,常数小很多。

inline int LCA(int x, int y) {
    if (dep[x] < dep[y]) swap(x, y);

    while (dep[x] != dep[y])
        x = fa[x][lg[dep[x] - dep[y]]];
    if (x == y) return x;

    for (int k = lg[dep[x]]; ~k; --k) {
        if (fa[x][k] ^ fa[y][k])
            x = fa[x][k], y = fa[y][k];
    }

    return fa[x][0];
}

唯一的问题是需要 \(O(n)\) 递推求一下 lg[x]\(\lfloor \log_2 x \rfloor\))数组即可。但这,并不会影响复杂度。

再次参考:算法学习笔记(3): 倍增与ST算法

那么问题来了,如何初始化?

显而易见,跳 2^k 步相当于跳 22^(k-1) 步,所以有了

fa[x][i] = fa[fa[x][i - 1]][i - 1];

复杂度分析

在初始化的时候每一个点都需要 \(O(\log n)\),那么总初始化需要 \(O(n \log n)\)

在询问时,令 kx , y 到最近公共祖先的最大距离,根据倍增算法,则复杂度为 \(O(\log k)\),当树退化成一条链时, k 最大取到 n ,那么最终复杂度应该为 \(O(\log n)\)

综上,初始化需要 \(O(n \log n)\) ,单次询问需要 \(O(\log n)\)

方法二:dfs序与ST表

这种方法相对难以理解,所以读者可以在掌握了一般的Tarjan缩点算法后再理解(这两个算法几乎没有关系,但是一些思想在Tarjan中有所体现)

下文中不是特别明白名词在后文中有所提及,或者可以参考讲解Tarjan算法的文章

先求出树每一个结点的 dfn ,不妨令 xy 更先遍历到( dfn[x] < dfn[y]

  • x 不是 y 的祖先

dfs 序列中,区间 [dfn[x], dfn[y]] 内一定包含了LCA子树的部分,但不包含LCA及其祖先,并且该区间一定包含了LCA到 y 路径上的第一个儿子,而且它的深度是最小的

所以,我们只需要找到区间 [dfn[x], dfn[y]] 中深度最小的点,它的父结点就是LCA

  • xy 的祖先,则 x 就是LCA,且 x 是区间 [dfn[x], dfn[y]] 中深度最小的点,与上述情况不太一样,那么考虑我们将 x 排除在区间外,则在区间 [dfn[x] + 1, dfn[y]] 中深度最小的点的父亲结点就是 x 。返回考虑第一种情况,由于第一种情况 x 一定不是LCA,那么将区间替换为 [dfn[x] + 1, dfn[y]] 不影响答案。

综上,我们只需要求区间 [dfn[x] + 1, dfn[y]] 中深度最小的点的父结点即可。

初始化与查询

定义 rdfn 满足 x == rdfn[dfn[x]] ,ST表初始化时 f[i][0] = rdfn[i]

其实可以只需要 dfn 就ok, f[dfn[i]][0] = i

定义区间操作

int Min(int x, int y) {
    return depth[x] < depth[y] ? x : y;
}

定义查询操作

int query(int x, int y) {
    if (x == y) return x; // 同一个结点啊
    // 确保x是先遍历到的那一个结点
    if (dfn[x] > dfn[y]) std::swap(x, y);
    int k = log(dfn[y] - dfn[x]);
    return Min(f[dfn[x] + 1][k], f[dfn[y] - (1<<k) + 1][k]);
}

其余的就套模板就行了。

再再次参考:算法学习笔记(3): 倍增与ST算法

复杂度分析

初始化其实主要是ST表的初始化,所以初始化的复杂度为 \(O(n \log n)\) (实际上应该是 \(O(n + n \log n)\)

查询也是ST表的区间查询,复杂度为 \(O(1)\)

方法三:树链剖分

好高级的名字……

树链剖分指将一棵树分割为若干条链,以维护树上信息。它包含重链剖分、长链剖分、实链剖分,在没有特殊说明的情况下,树链剖分一般指代重链剖分。这里也着重描述重链剖分。

这里先给出一些

DFS序

dfs序指dfs的顺序。具体方法是用一个计数变量cnt,遍历到结点x时,时间戳 dfn[x] = ++cnt ,对应dfs序列中第cnt个就是x

而上文定义中的 rdfn 则可以在同时通过 rdfn[cnt] = x 记录下来

性质
  • 结点的 dfn 大于其任意父结点

  • 对于任意结点(包含本身)的子树中,存在一个 dfn 是连续的一条链

如果子树在dfs序列中是连续的一段,在维护子树(子树求和之类的子树操作)时,直接把它看做一个序列,那么就和在线段树上操作没有区别了

重链

相邻重边链接形成的链

重边

重子结点(如果有)与其父结点相连的边

重子结点

一个结点的子结点中度最大的结点(孩子个数最多的点)

剖分方法

重链剖分就是将每一条重链单独划分出来,从而通过 dfn 来维护链上信息

至于如何剖分,需要进行两次遍历

第一次遍历,获得所有节点的 siz , dep , fa , son

这里 siz 指结点的度,三个字符统一一下,fa是个例外dep 指结点的深度, fa 指结点的父结点, son 指结点的重子结点

第二次遍历,获得所有点的 dfn , top

这里 dfn 无需解释, top 指结点所在重链最顶部的结点

思路清晰,这里给出一种参考写法

注意前提,点编号从 1 ~ n ,且这里用的是前向星存图(树)

int top[N], dfn[N], son[N], dep[N], siz[N], fa[N];
// work son, siz, dep and fa
void workSSDF(int x, int par) {
    dep[x] = dep[par] + 1, fa[x] = par, siz[x] = 1;
    for (int y, i = head[x]; i; i = edge[i].next) {
        y = edge[i].to;
        if (y == par) continue;
        workSSDF(y, x);
        siz[x] += siz[y];
        if (siz[y] >= siz[son[x]]) son[x] = y;
    }
}

// work dfn and top
int cdfn = 0;
void workDT(int x, int ptop) {
    dfn[x] = ++cdfn, top[x] = ptop;
    if (son[x]) workDT(son[x], top[x]);

    for (int y, i = head[x]; i; i = edge[i].next) {
        y = edge[i].to;
        if (!dfn[y]) workDT(y, y);
    }
}

剖分作用

这么麻烦的求这个树链剖分有啥用?

如果我们随便画一个图并模拟一下上述过程……

graph TD; A[结点编号] 1---2; 1---3; 3---4; 3---5; 3---7; 4---8; 8---9; 5---6;

在两次遍历完之后:

graph LR; A[结点上的是dfn序] subgraph 重链1 1 === 2; 2 === 3; 3 === 4; 4 === 5; end subgraph 重链2 6 === 7; end subgraph 重链3 2 --- 8 end subgraph 重链4 1 --- 9 end 2 --- 6

考虑用纯markdown画图是真的难受,但树的结构是一样的……T^T

我们很容易发现,在同一条重链上的结点的 dfn 序是连续的……(这我们稍后在论述)

回到求LCA的流程,由于我们把树分为了从上到下的一些链

注意每一条链中没有深度相同的结点

所以,我们只需要不断的把两个结点通过 top 向上跳直到在同一条链上(此时 top[x] == top[y]

至于为什么要跳 top 结点的深度较大的结点……还请读者自行讨论

有一个需要注意的地方,不能直接 x = top[x] ,因为 top[top[x]] == top[x] !!!

所以还需要跳到 top[x] 的父节点上

流程清晰,这里给出一种参考代码

int lca(int x, int y) {
    while (top[x] != top[y]) {
        if (dep[top[x]] >= dep[top[y]]) x = fa[top[x]];
        else y = fa[top[y]];
    }
    if (dep[x] <= dep[y]) return x;
    return y;
}

复杂度分析

太难写了 Q^Q

依据重链的定义,每一条重链至少占了重链顶端结点所在的子树结点的 \(\log n\) 个结点(一条链就占满了)

所以,剖分之后差不多是有 \(\log n\) 条重链,所以每次询问至多跳 \(\log n\) 次,所以……

初始化复杂度为 \(O(n)\) (两次dfs),查询复杂度为 \(O(\log n)\),当查询与点数同阶时快于倍增。并且空间复杂度更加优秀,为 \(O(n)\),只是常数为 \(7\)

树链剖分拓展

看我的另一篇文章吧,太难写了,四千多个字呜啊

与算法学习笔记(5): 最近公共祖先(LCA)相似的内容:

算法学习笔记(5): 最近公共祖先(LCA)

树上最近公共祖先(LCA)三种求法:倍增,DFS+ST表,熟练剖分

算法学习笔记(6): 树链剖分

树链剖分 树链剖分是一个很神奇,但是在树上可以完成一些区间操作问题 简单来说,就是把一棵树分成一条条的链,通过维护链上的信息来维护整棵树的信息 基础知识可以参考我的另外一篇博客:算法学习笔记(5): 最近公共祖先(LCA) 这里假设你已经掌握了上述博客中的所有相关知识,并清晰了其背后的原理 性质?发

算法学习笔记(16): 组合数学基础

组合数学基础 本文部分运用到了生成函数的知识 如果直接食用本文结论,请忽略下列链接。 生成函数参考博客:普通型生成函数 - Ricky2007 - 博客园 我认为讲的不错 组合数学非常有用!我们先从一点点简单的性质开始 简单原理 加法原理 这非常简单,我们举一个例子即可:考虑我有 $5$ 个红苹果和

给大家分享一套非常棒的python机器学习课程

给大家分享一套非常棒的python机器学习课程——《AI小天才:让小学生轻松掌握机器学习》,2024年5月完结新课,提供配套的代码+笔记+软件包下载!学完本课程,可以轻松掌握机器学习的全面应用,复杂特征工程,数据回归,分类,算法的项目实战应用,以小学生的视角和知识储备即可学会。课程名字:AI小天才:

算法学习笔记(11): 原根

原根 此文相对困难,请读者酌情食用 在定义原根之前,我们先定义其他的一点东西 阶 通俗一点来说,对于 $a$ 在模 $p$ 意义下的阶就是 $a^x \equiv 1 \pmod p$ 的最小正整数解 $x$ 或者说,$a$ 在模 $p$ 意义下生成子群的阶(群的大小) 再或者说,是 $a$ 在模

算法学习笔记(30):Kruskal 重构树

Kruskal 重构树 这是一种用于处理与最大/最小边权相关的一个数据结构。 其与 kruskal 做最小生成树的过程是类似的,我们考虑其过程: 按边权排序,利用并查集维护连通性,进行合并。 如果我们在合并时,新建一个节点,其权值为当前处理的边的权值,并将合并的两个节点都连向新建的节点,那么就可以得

算法学习笔记(3.1): ST算法

ST表 在RMQ(区间最值)问题中,著名的ST算法就是倍增的产物。ST算法可以在 \(O(n \log n)\) 的时间复杂度能预处理后,以 \(O(1)\) 的复杂度在线回答区间 [l, r] 内的最值。 当然,ST表不支持动态修改,如果需要动态修改,线段树是一种良好的解决方案,是 \(O(n)\

C++算法之旅、09 力扣篇 | 常见面试笔试题(上)算法小白专用

算法学习笔记,记录容易忘记的知识点和难题。详解时空复杂度、50道常见面试笔试题,包括数组、单链表、栈、队列、字符串、哈希表、二叉树、递归、迭代、分治类型题目,均带思路与C++题解

C++算法之旅、08 基础篇 | 质数、约数

算法学习笔记,记录容易忘记的知识点和难题。试除法、分解质因数、筛质数、约数个数、约数之和、最大公约数

算法学习笔记(1): 欧几里得算法及其扩展

扩展欧几里得算法详解 在了解扩欧之前我们应该先了解欧几里得算法 欧几里得算法 这是一个递归求最大公约数(greatest common divisor)的方法 $$ gcd(a, b) = gcd(b, a % b) $$ 可以通过一个类似的简单公式推导而来 好像叫做辗转相减法来着? $$ gcd(