视频字幕
树链剖分是一种重要的树上数据结构技术。它的核心思想是将树分解为若干条链,通过重儿子和轻儿子的概念来实现。对于每个节点,我们选择子树大小最大的儿子作为重儿子,其他儿子称为轻儿子。连接父节点和重儿子的边叫重边,用红色表示;连接父节点和轻儿子的边叫轻边,用灰色表示。这样的划分为后续的LCA查询奠定了基础。
现在我们来看重链的划分过程。从根节点1开始,它的重儿子是节点2,所以形成第一条重链。节点2的重儿子是节点5,继续延伸重链1。节点3有两个儿子,子树大小相同,我们选择节点6作为重儿子,形成重链2。节点7形成重链3。节点4是叶子节点,单独成链。这样整棵树被划分为4条重链。重要的是,任意两点间的路径最多经过对数级别的重链,这保证了查询的高效性。
DFS序与链顶标记是树链剖分的关键预处理步骤。第一次DFS从根节点开始,计算每个节点的深度、子树大小、父节点和重儿子信息。第二次DFS进行链剖分,为每个节点标记其所在重链的链顶。我们可以看到,节点1、2、5在同一条重链上,它们的链顶都是1。节点3、6在一条重链上,链顶是3。节点4和7各自单独成链。DFS序记录了遍历的顺序,这对后续的区间操作很重要。
现在演示LCA查询算法的具体过程。假设我们要查询节点4和节点6的最近公共祖先。首先检查它们是否在同一条重链上,节点4的链顶是4,节点6的链顶是3,不在同一链上。接下来,我们让深度更大的链顶向上跳跃。节点4跳到父节点2,现在比较节点2和节点6,它们的链顶分别是1和3,仍不在同一链上。继续让节点6跳到父节点3,再让节点3跳到父节点1。最终节点2和节点1在同一条重链上,返回深度较小的节点1作为LCA。整个过程时间复杂度为O(log n)。