ACM竞赛算法模板：Tarjan LCA与RMQ-ST详解

本文主要介绍了ACM算法中的两个常用模板：Tarjan算法求最近公共祖先（LCA）和RMQ-ST算法（一维及二维的最近最值查询）。这两个算法在解决图论问题和数组查询优化中具有重要作用。 1. Tarjan算法求最近公共祖先（LCA） Tarjan算法是一种基于Disjoint Set的数据结构来计算二叉树中两点的最近公共祖先的方法。算法步骤如下： - 首先对每个节点调用`Make-Set`，创建一个集合并把节点自身设为集合代表。 - 初始化`ancestor`数组，用于存储每个集合的祖先节点，并将当前节点设为其祖先。 - 遍历节点u的所有孩子v，递归地调用`LCA(v)`，然后使用`Union`操作合并集合，更新祖先节点。 - 标记节点u为已检查(`checked[u]=true`)，并处理所有边(u, v)，如果v也已检查，就返回u和v的祖先，即`ancestor[Find-Set(v)]`。 2. RMQ-ST算法（最近最值查询） RMQ-ST算法是一种在一维和二维数组中进行快速查询最小（或最大）值的算法，初始化和查询操作的时间复杂度分别为O(n log n)和O(1)。 - 在一维数组中，`Sparse Table`(稀疏表)用于存储不同长度区间内的最小值。首先，将区间长度为1的最小值初始化到m数组。然后，逐层构建更长的区间，比较相邻区间的最小值并存储结果。 - 查询操作时，通过计算查询范围长度对应的二进制位数k，找到对应长度的区间，返回m数组中的对应元素，即为查询范围内的最小值。 对于二维数组的RMQ，可以扩展该算法，处理矩阵中的最近最值查询，原理类似，但需要额外的二维存储结构。 这些算法在ACM竞赛和实际编程中非常实用，特别是在处理图的遍历和动态查询优化等问题时。熟练掌握它们能够提升解题效率，为图论和数组处理问题提供高效解决方案。