Tarjan算法：高效解决RMQ与LCA问题

"本文主要介绍了 Tarjan 算法在解决 RMQ（区间最小值询问问题）和 LCA（最近公共祖先问题）中的应用。Tarjan 算法是一种离线算法，其时间复杂度为 O(Nα(N) + Q)，其中 N 是问题规模，Q 是询问次数，α(N) 表示逆阿克曼函数，通常 α(N) 的增长极其缓慢，接近常数。" Tarjan 算法是解决有根树中最近公共祖先（LCA）问题的一种高效方法。在有根树中，LCA 问题询问的是给定两个节点 u 和 v，在树中是否存在一个节点 x，它既是 u 的祖先也是 v 的祖先，并且 x 到根的距离是最远的。Tarjan 算法通过一次深度优先搜索（DFS）来一次性处理所有的 LCA 询问，同时利用并查集的数据结构来维护树的信息。 区间最小值询问问题（RMQ）则是在一个线性序列 A 中，找出给定区间 [i, j] 上的最小值。对于 RMQ 问题，存在多种解决方案，例如 ST 算法，它在预处理阶段需要 O(N log²N) 的时间，之后每次询问可以在 O(1) 时间内完成。如果线性序列 A 的相邻元素相差 ±1，则这种 RMQ 问题被称为 ±1 RMQ，可以有更高效的算法来解决。 RMQ 问题与 LCA 问题之间存在转化关系，这意味着解决其中一个问题的方法可能对另一个问题也有用。例如，通过将树的边权值设置为节点之间的距离，可以将 LCA 转化为 RMQ 问题，反之亦然。这种转化使得某些算法在处理 RMQ 或 LCA 时能有更广泛的应用。 在信息学竞赛中，RMQ 和 LCA 问题是常见的题目类型，如上海2003年省选的登山问题和2002年 POI 的商务旅行等。熟练掌握这两类问题的解决策略对于参赛者来说至关重要。 Tarjan 算法相比于其他算法，其时间复杂度中的 α(N) 函数使得它在处理大规模数据时具有优势，因为 α(N) 几乎是一个常数。例如，ST 算法虽然预处理时间较长，但在每次询问时非常快；而 ±1 RMQ 算法则在处理特定类型的 RMQ 问题时表现出色。 Tarjan 算法在处理 LCA 问题上提供了有效且高效的方法，尤其适合于离线场景，即所有询问在算法开始前已知的情况。结合 RMQ 问题，这个算法在实际应用和竞赛中都有广泛的价值。