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. 到同一高度后,同时往上移动,一个一个移动肯定很慢啊,怎么办呢还是利用二进制啊,倍增好像就是这样,用二的次幂处理,我们可以倒着尝试移动,从直接移动log2(n)(why? log2(n)就是移动$2^{log_2(n)}$次肯定会移动到最上面滴)如果相等,那就是在移动$2^{log_2(n)}$之前就有可能找到一个相同点,那么这个就不移动,继续找,最后这个点的父节点就是最近公共祖先

  3. 例子就没必要了,自己推吧

  4. 代码

    1
    待补充
LCA 转化成RMQ
RMQ 算法介绍

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

如果对您有帮助,请小小支持一下,您的支持将鼓励我继续创作!
0%