最近公共祖先 算法总结
现知LCA算法有倍增、Tarjan、树链剖分
再LCA问题上各自的特点如下表
| 倍增 | Tarjan | 树链剖分 | |
|---|---|---|---|
| 数组 | fa[u][i], dep | fa, vis, query, ans | fa, dep, size_tree, heavy_child, top_chain |
| 思路 | 深搜打表，跳跃查询 | 深搜回溯，离线查询 | 二重深搜打表，跳跃查询 |
| 时间复杂度 | O((n+m)logn) | O(n+m) | O(n+mlogn) |
| 链接 |
现知LCA算法有倍增、Tarjan、树链剖分
再LCA问题上各自的特点如下表
| 倍增 | Tarjan | 树链剖分 | |
|---|---|---|---|
| 数组 | fa[u][i], dep | fa, vis, query, ans | fa, dep, size_tree, heavy_child, top_chain |
| 思路 | 深搜打表，跳跃查询 | 深搜回溯，离线查询 | 二重深搜打表，跳跃查询 |
| 时间复杂度 | O((n+m)logn) | O(n+m) | O(n+mlogn) |
| 链接 |