LCA, 全称叫做最近公共祖先, 这是在树结构中的一个算法, 来求解一棵树中两个节点的最近公共祖先, (其实就是字面意思
关于LCA的求法, 常见的大概有3种, 效率也都不很一样:
- 向上标记法求LCA
- 树上倍增法求LCA
- LCA 的 Tarjan 算法
由于第一种算法十分暴力, 直接就是根据 LCA 的定义暴力求解, 所以就不多加解释, 第二第三种方法的时间复杂度都比较优秀, 不同的是 树上倍增 支持在线处理, 而 Tarjan 算法只支持离线操作, 但是复杂度都是可以接受的, 需要根据题目来酌情选择
树上倍增求LCA
时间复杂度: O(nlogn) + O(logn) 预处理+询问