链剖树(Link-Cut Tree)

链剖树又称动态树,是一种维护森林并支持结构动态变化的高级数据结构。它用若干伸展树表示对森林的实链剖分,能在树的形态不断连边、断边的过程中,高效回答路径上的各种查询。

概述

链剖树由丹尼尔·斯利特(Daniel Sleator)与罗伯特·塔扬于1980年代提出。它把森林中的每条路径拆成若干实链与虚链,每条实链用一棵伸展树维护。通过一个称为访问的核心操作,可以把任意节点到其所在树根的路径整合成一条实链,进而支持路径修改与查询。

核心原理

• 实链剖分:把每个节点到其某个孩子的边分为实边或虚边,实边连成的链用伸展树表示。
• 访问操作:把指定节点到根的路径全部变为实边,是所有操作的基础原语。
• 换根:通过区间翻转标记,可把任意节点提升为整棵树的根。
• 连边与断边:在两棵动态树之间加边或删边,配合访问维护实链结构,单次操作摊还对数复杂度。

应用场景

链剖树用于解决动态树上的连通性、路径求和、路径最值以及维护生成树等问题,是许多在线图算法的基石。它常见于算法竞赛中的动态树题目,也是某些网络流与动态最小生成树算法的加速工具。

常见问题

问:链剖树和树链剖分有何不同?答:树链剖分处理的是形态固定的静态树上的路径问题;链剖树能处理树形态动态变化的情形,可连边断边,适用范围更广但常数更大。

问:为什么用伸展树而非其他平衡树?答:伸展树天然支持区间的分裂合并与翻转标记,且其摊还特性与访问操作的势能分析契合,使整体复杂度维持在摊还对数级。