LCA的Tarjan离线快速算法具体是怎样的？
- 内容介绍
- 文章标签
- 相关推荐
本文共计667个文字，预计阅读时间需要3分钟。
最常见LCA（树上公共祖先）算法都是基于线段树，往往带有log复杂度。一种方法是转化为-1最大值问题，得到O(n)+O(1)的复杂度，但原理复杂，常量大。今天介绍一种允许离线时接近线性性求近似值的方法。
最常见的LCA（树上公共祖先）都是在线算法，往往带了一个log。有一种办法是转化为“+-1最值问题”得到O(n)+O(1)的复杂度，但是原理复杂，常数大。今天介绍一种允许离线时接近线性求LCA的Tarjan算法。
一个点和其他点的LCA必定是它到root路径上的所有节点之一，而另一个节点刚好在哪个节点下，LCA就是谁：
如图，标粗的箭头为当前搜索的路径，左边为已经搜索完毕的路径，右边的黑色节点尚未搜索。现在要求节点cur和节点a的LCA，显然a是什么颜色，LCA就也是这个颜色，如果a还没有被搜索到，那就不处理，把这个询问留给搜索到a的时候处理（那个时候cur肯定已经访问过了）。
本文共计667个文字，预计阅读时间需要3分钟。
最常见LCA（树上公共祖先）算法都是基于线段树，往往带有log复杂度。一种方法是转化为-1最大值问题，得到O(n)+O(1)的复杂度，但原理复杂，常量大。今天介绍一种允许离线时接近线性性求近似值的方法。
最常见的LCA（树上公共祖先）都是在线算法，往往带了一个log。有一种办法是转化为“+-1最值问题”得到O(n)+O(1)的复杂度，但是原理复杂，常数大。今天介绍一种允许离线时接近线性求LCA的Tarjan算法。
一个点和其他点的LCA必定是它到root路径上的所有节点之一，而另一个节点刚好在哪个节点下，LCA就是谁：
如图，标粗的箭头为当前搜索的路径，左边为已经搜索完毕的路径，右边的黑色节点尚未搜索。现在要求节点cur和节点a的LCA，显然a是什么颜色，LCA就也是这个颜色，如果a还没有被搜索到，那就不处理，把这个询问留给搜索到a的时候处理（那个时候cur肯定已经访问过了）。