算法5 16
-
最近公共祖先LCA(倍增思想)
定义最近公共祖先简称LCA(Lowest Common Ancestor)。两个节点的最近公共祖先指的是这两个点的公共祖先中离根最远的那个。
-
ST表算法与代码实现
对于区间最值也就是 RMQ(Range Minimum/Maximum Query)问题,可以使用ST表(稀疏表)的方式进行离线预处理。ST表思想与原理ST表的核心思想是倍增。
定义最近公共祖先简称LCA(Lowest Common Ancestor)。两个节点的最近公共祖先指的是这两个点的公共祖先中离根最远的那个。
对于区间最值也就是 RMQ(Range Minimum/Maximum Query)问题,可以使用ST表(稀疏表)的方式进行离线预处理。ST表思想与原理ST表的核心思想是倍增。