Splay 操作与势能分析与 Link-Cut Tree 与 Top Tree

• LCT 维护森林的动态树操作：link/cut/路径查询
• 动态连通性、动态 MST、动态路径最值
• 均摊 O(log n) 操作

Link-Cut Tree（LCT）用"实链剖分 + splay 辅助树"维护动态森林，支持 link（连边）、cut（断边）、makeroot（换根）、路径查询（最值/和/异或）等操作，均摊 O(log n)。工业应用：动态图连通性——维护森林的连通分量，边插入/删除时判断是否连通；动态 MST——在允许加边/删边的图中维护最小生成树，插入边时若成环则替换环上最大边；动态路径——在线查询 u 到 v 路径上的最值/和。LCT 让这些原本需要重算的树上动态问题在线更新。它是"动态树"家族的核心，配合子树信息扩展可处理动态子树问题。

LCT 的价值是把"动态树上的路径/连通性"问题变成 O(log n) 的在线操作。核心是实链剖分与 splay 辅助树。动态 MST 是经典应用：加边成环时用 LCT 找环上最大边替换。理解"link/cut/路径查询"三操作是掌握 LCT 应用的基础。

• access 把到根路径改为实链，虚实边切换发生在 preferred path 上
• 用"轻边计数"证明每次切换次数均摊 O(log n)
• splay 势能（Σlog size）与 access 势能合并

LCT 的 access(x) 把从 x 到根的路径全部变成实链（preferred path），过程中会发生虚实边切换：每切一条实边换一条虚边。摊还分析的关键是"虚实切换次数"：用每个节点的"轻儿子"（子树大小不超过一半的虚儿子）计数，一个节点最多有 O(log n) 个轻虚祖先；每次 access 的交替切换中，实轻边切换会产生 O(log n) 的势能积累，因此总切换次数均摊 O(log n)。分析将 splay 势能（每个 splay 树用 Σ log(size) 作势能）与 access 的虚实切换势能（轻虚边计数）合并：access 内部的 splay 操作由 splay 势能保证 O(log n) 摊还，虚实切换由轻边计数保证 O(log n) 摊还，两者叠加得到 LCT 整体 O(log n) 摊还。这是官方证明的框架。

摊还的难点在于"虚实切换"的数量。用轻边（size 减半的虚边）结构证明：每个节点到根的路径上轻边 O(log n)，且每次 access 的实虚切换可与轻边势能绑定，从而均摊 O(log n)。splay 势能保证 splay 自身的摊还，两类势能合并得整体界。

• access：打通到根的实链
• rotate/splay：辅助树旋转与伸展
• link/cut：连边与断边

LCT 的核心操作：access(x) 把 x 到根的路径变为实链，返回这条链的 splay 根；splay(x) 把 x 伸展到其辅助树根；rotate 是 splay 的旋转。makeroot(x) = access(x) + splay(x) + 反转标记（把 x 变成树根）。link(x,y) = makeroot(x) + 把 x 的父设成 y（确认无环）；cut(x,y) = makeroot(x) + access(y) + 把边断开。路径查询 query(u,v)：makeroot(u) + access(v) + splay(v)，此时 v 的 splay 子树即 u-v 路径的聚合信息，可直接读取。每个操作内部一次或几次 access + splay，均摊 O(log n)。路径查询的关键是"makeroot + access 把路径聚到一棵辅助树"。

路径查询通过"makeroot(u) 让 u 成根，access(v) 把 u-v 路径打通成一条实链，聚合到 v 的 splay"实现。各操作共享 access/splay 骨架，均摊 O(log n)。理解"实链聚合路径"是核心。

• preferred edge：实边（通向最近访问的子节点）
• preferred path：实边组成的链
• access/expose 把到根路径变为 preferred path

LCT 中，每个节点最多有一条 preferred edge（实边），指向其"最近被访问"的子节点；由 preferred edge 连成的链叫 preferred path（实链）。非实边（虚边）连接不同的 preferred path。access/expose(x) 的核心操作是：把从 x 到根路径上的所有边都改成实边（preferred edge），并把 x 变成该路径的末端（最深），其余原有实边变为虚边。工程细节：access 涉及"沿虚边向上、把每个经过节点的实儿子变成虚（断开）、把新路径节点设为实儿子、splay 伸展"的循环。通过 update 维护聚合信息，反转标记处理方向的改变。preferred path 的动态变化是 LCT 支持动态树的基础。

preferred path 是"最近访问行为"的实链划分，access 根据访问动态调整虚实划分。工程上 access 的循环遍历虚边，逐层"断开实儿子、连上路径节点、splay"。理解 preferred edge 的"最近访问"语义是 access 的关键。

• Top Tree 用簇（cluster）表示树结构
• compress：合并路径上的簇
• rake：合并叶节点/分支

Top Tree 是动态树的通用抽象，把树划分成簇（cluster），每个簇是一棵子树（由若干边和边界节点组成），支持 Rake 与 Compress 两种合并操作构建簇树。compress 把沿路径的簇合并（保留原路径的边界节点），rake 把叶节点/分支并入相邻簇（绑定到一个边界节点）。Rake/Compress 配合 blast 表达式的树形态化简，把整个树化简成单个簇，从而支持路径与子树查询。边界节点（boundary node）是簇中与外部相连的节点（最多 2 个），处理时需维护其作为聚合信息的锚点。Top Tree 的簇抽象把 LCT 的"链"推广到"任意连通子图"，是更一般、更复杂的动态树框架。

Top Tree 的核心是"簇 + Rake/Compress 化简"。compress 合并路径、rake 合并分支，边界节点定义簇的接口。相比 LCT 只维护链，Top Tree 通过簇处理更复杂的动态树问题（如动态子树、动态最小割）。

• 路径加/乘懒标记的优先级与组合
• rev 反转标记与路径标记的交互
• makeroot 后聚合信息更新

LCT 的懒标记支持路径加/乘与 rev 反转。组合规则：先乘后加（区间乘 m 加 a 时，节点值 = 值*m + a，标记按 m,a 更新）；当加与乘同时存在时，需定义标记的合成顺序（如新标记压到旧标记上时，先乘后加）。rev 标记用于 makeroot 换根时反转路径方向，它只影响左右子顺序，不影响值聚合的"和/最值"（但影响"方向相关"的聚合如前缀/后缀最大值）。下传顺序：push_down 时先下传 rev，再下传加/乘（或按定义顺序），保证子节点状态正确。makeroot 后聚合更新：makeroot = access + splay + rev，反转标记挂在节点上，push_up 时按当前左右子顺序聚合。关键是"标记组合的优先级 + 下传顺序 + 聚合的方向性"。

复杂懒标记的核心是"优先级与顺序"：先乘后加定义组合，rev 与加/乘独立但需统一下传顺序。聚合若方向相关（如最大子段和），rev 反转后需交换左右聚合。理解"标记合成 + 下传顺序"是 LCT 懒标记正确性的关键。

• 实链剖分：把树分成实链（preferred path）
• Splay 辅助树维护每条实链
• access/makeroot 维护路径

Link-Cut Tree 的原理是"实链剖分 + Splay 辅助树"：把树按"最近访问"划分成若干实链（preferred path），每条实链用一棵 Splay 辅助树维护（按深度为键）。access(x) 把 x 到根的路径打通成一条实链，并在此过程中维护各辅助树的指针与聚合信息。makeroot(x) 通过 access(x) + splay(x) + 反转标记把 x 变成整棵树根，从而改变路径方向。路径信息（如 u-v 路径最值/和）通过 makeroot(u) + access(v) 把 u-v 路径聚到一棵辅助树，读取该树根聚合即可。虚边（不同实链间）用"辅助树根指向父节点"的指针表示。LCT 靠这种虚实划分动态维护路径。

核心是"实链剖分把动态路径变成若干 splay 辅助树"。access 打通路径、makeroot 换根，通过虚实边调整与 splay 聚合维护路径信息。理解"实链 + splay + 虚实划分"是 LCT 原理。

• makeroot 换根需反转路径使 x 变根
• rev 标记表示辅助树左右子反转
• 方向相关聚合（如最大子段和）在反转后需交换

makeroot(x) 把 x 变成整棵树的根。因为 access(x) 只是把 x 到根的路径打通成实链，此时 x 在辅助树的最深（最大深度）位置；要变成根，需要把这条路径的深度方向反转，即对辅助树打反转标记（rev），使 x 变成最浅。rev 标记在 push_down 时交换左右儿子并下传，实现"序反转"而不必实际移动节点。换根改变 preferred path 的方向：makeroot 后原路径的根与叶交换，preferred path 的深度顺序反转。信息聚合处理：若聚合是"方向无关"的（和、最值），rev 不影响；若是"方向相关"的（如最大前缀/后缀和、最大子段和），反转后需交换前缀与后缀聚合值。makeroot 是 link/cut 与路径查询的基础。

rev 标记是"懒反转"：用 O(1) 标记代替实际 O(n) 调整。makeroot 通过反转路径实现换根。方向相关聚合需在 push_up 时按当前方向交换前后缀。理解"rev 懒标记 + 方向聚合"是 makeroot 正确性关键。

• 动态连通性：link/cut + findroot
• 路径最值：makeroot + access + 聚合
• 子树操作：需额外维护虚子树信息

LCT 的典型应用：动态连通性——用 link/cut 维护森林，findroot(x) 判断连通（access + splay，沿左子到底）；动态路径最值——makeroot(u) + access(v) + splay(v) 后读取 v 的聚合值即 u-v 路径最值；子树操作——标准 LCT 只能维护链信息，要维护子树（虚子树）需额外记录虚子树贡献（在 access/link 时更新虚边聚合），即"虚子树信息 + 实子树信息"的合并。典型题如动态 MST、动态树上路径修改/查询、动态连通性计数。子树操作是 LCT 的进阶应用，需要维护虚子树聚合。

动态连通性靠 findroot，路径最值靠 makeroot+access 聚合，子树操作需额外虚子树信息。理解"标准 LCT 维护链、子树需扩展虚子树"是区分应用场景的关键。

• 标准 LCT 的聚合只覆盖实链（辅助树）
• 虚子树信息跨链，不进入辅助树聚合
• 实现：在 access/link 时维护虚子树贡献

标准 LCT 的每个 splay 辅助树只维护一条实链（preferred path）的节点，聚合（sum/max）只统计实链内的节点。但一个节点的子树包含其虚儿子（通过虚边连接的其他实链）的整棵子树，这些信息不在当前辅助树内，因此标准 LCT 无法直接得到子树聚合。要维护子树信息，需额外记录"虚子树贡献"：对每个节点维护其为虚根的子树大小/和/最大值，在 access 打虚实切换时（实儿子变虚、虚变实）更新虚子树聚合；在 link/cut 时也要更新父节点的虚子树信息。实现上，每个节点单独存 sub（虚子树聚合）与 len（实链聚合），聚合 = 实链聚合 + 虚子树聚合。这样就能查询任意节点的子树信息。

局限源于"辅助树只覆盖实链"。维护子树的关键是"把虚子树贡献单独记录并随虚实切换更新"。理解"实链聚合 + 虚子树聚合"的分离是扩展 LCT 做子树操作的核心。

• Splay 每次访问把节点摊到根，近期访问节点靠近根
• 静态最优性/工作集定理：频繁访问的节点开销小
• 缓存局部性强的场景收益

Splay 树是自调整平衡树：每次访问（查找/插入）都通过 splay 把被访问节点旋转到根，使最近访问的节点位于树的浅层。访问序列最优性（Access Sequence Optimality）指 Splay 树总能在任意访问序列上达到渐近最优（不存在静态最优搜索树能显著优于它），这是 Splay 树的理论优势。工作集定理（Working Set Theorem）更具体：频繁访问的"工作集"节点会保持在浅层，访问代价与其上次访问时间相关。在缓存局部性强的工程场景（如访问分布高度倾斜、热点数据集中）中，Splay 树把热点节点摊到根，命中率极高、常数小，比静态 BST 更优。工程实现上，Splay 无需平衡因子，用 zig/zig-zig/zig-zag 旋转，无额外内存，适合高倾斜访问。

Splay 的价值是"自调整 + 访问序列最优性"：热点自动上浮。访问序列最优性保证理论最优，工作集定理解释实际收益。缓存局部性强（热点集中）时收益最大。理解"自调整到根"是核心。

• Splay 通过旋转调整，访问局部性好但需多次旋转
• Treap 是随机平衡，结构随机化影响缓存
• cache miss 与分支预测的实测差异

在大量操作（如 10^8 数量级）下，Splay 与 Treap 的实测性能差异体现在 cache 与分支预测。Splay 树把热点节点旋到根，访问局部性好，热点在浅层、缓存命中率高；但每次 splay 涉及多次旋转（多个指针修改），指令多、分支多，若访问随机则旋转分支预测命中率低。Treap 是完全随机的平衡树（随机优先级），形状期望平衡，访问路径深度稳定 O(log n)，但随机形状导致缓存命中率较低（节点分散），且查找只有一次比较分支（分支预测良好）。实测趋势：访问分布倾斜时 Splay 因工作集定理缓存命中高、总体快；访问均匀随机时 Treap 因结构稳定、分支预测好而更稳。具体取决于数据分布与实现细节。

差异核心是"自调整缓存局部性 vs 随机结构的稳定性"。Splay 倾斜访问优、随机访问旋转开销大；Treap 随机访问稳定、缓存分散。工程选择取决于访问分布。这些是实测观察到趋势，需结合具体实现。

• Splay 自调整：热点上浮，skew 分布下缓存/访问优
• Skip list 随机层，结构固定，无自调整
• skew 分布下的实测差异

在 workload skew（访问高度偏斜，少数热点被频繁访问）分布下，Splay 与跳表表现出明显差异。Splay 通过 splay 把热点节点旋转到根，热点访问 S 成本极低（近 O(1)），工作集定理保证热点在浅层，总体平均访问代价低，非常适合 skew 分布。跳表（skip list）结构固定（随机层数建好后不随访问调整），热点与冷点访问路径长度接近（都是 O(log n) 期望），无法利用访问偏斜，因此 skew 分布下平均开销高于 Splay。实测中，skew 分布下 Splay 平均访问时间显著低于跳表；但代价是 Splay 的旋转会增加常数，且若访问均匀（无 skew）则 Splay 的优势消失甚至略慢。跳表优势在实现简单、并发友好、无重组。

差异核心是"是否自调整"。Splay 自调整利用 skew（热点上浮），跳表静态结构无法利用。skew 分布下 Splay 优、均匀分布下跳表更稳。理解"自调整 vs 静态"是选型关键。

• Top Tree 用簇（cluster）表示树，Sleator-Tarjan 提出
• cluster forest：簇的树/森林结构
• Rake/Compress 合并簇

Splay Top Tree 是 Sleator & Tarjan 提出的一类动态树抽象，用簇（cluster）把树组织成"簇树/簇森林"（cluster forest）。每个簇是有界节点数（通常 2 个边界节点）的连通子图，簇之间通过 Rake 与 Compress 操作合并成更小的簇树，最终单个簇代表整棵树。Compress 操作合并沿路径（把两个簇首尾相接成新簇，公共边界节点保留），Rake 操作合并叶/分支（把无外部边的小簇并入主簇）。Splay 拓扑树（Link-Cut Top Tree）用 splay 辅助树维护簇的合并序列，使 Rake/Compress 操作摊还 O(log n)。cluster forest 的组织方式使 Top Tree 能支持比 LCT 更丰富的动态树问题（路径与子树、动态最小割等）。

Top Tree 的核心是"簇 + Rake/Compress 化简 + cluster forest 组织"。Sleator-Tarjan 用 splay 维护簇合并摊还 O(log n)。理解"簇抽象比链更一般"是 Top Tree 与 LCT 关系的核心。

• 竞赛 Splay 用数组模拟、静态节点、简洁
• 工业 Splay 用对象/指针、更重封装
• 常数因子差异与适用场景

Codeforces 14D（Two Paths，求树上两条不相交路径长度乘积最大）等题目用 Splay 时，竞赛实现追求常数最小：用静态数组模拟节点（ch[2]、fa、rev 等 int 数组）、避免动态分配、无对象封装、紧凑内存布局，常数很小。工业实现（如 C++ STL 相关或生产库）通常用对象/指针、封装度高、可能带异常处理与迭代器，常数因子大，但更可维护、安全性好。差异来源：静态数组 vs 堆/对象分配、迭代 vs 递归、无封装 vs 多层抽象。竞赛在时限内选常数小的数组实现，工业选可维护的封装实现。同一算法，常数可能差数倍。

常数因子差异源于"内存布局与封装"：静态数组紧凑、缓存友好、无分配开销；对象封装有分配与虚函数等开销。竞赛与工业对"常数 vs 可维护"的取舍不同。理解"实现方式决定常数"是关键。

• 静态最优性：Splay 达到最优静态搜索树的总代价
• 工作集定理：访问代价与上次访问时间相关
• 工程应用：热点数据、缓存、自适应结构

Splay 树的静态最优性定理（Static Optimality Theorem）指出：对于任一访问序列，若 Splay 树的访问代价比任何静态最优二叉搜索树（即固定形状、遍历代价的下界）的代价高，则高出的部分是 O(n) 的（即渐近最优），这是 Splay 动态调整强大能力的保证。工作集定理（Working Set Theorem）更强：Splay 树中访问一个节点 x 的代价与"x 上次被访问以来访问过的不同节点数"（即工作集大小）相关，访问越频繁（工作集越小）的节点越浅、代价越低。工程应用：Splay 树适合访问分布高度偏斜、"工作集"不断变化的场景（缓存、热点键、自适应 index），能自动把热点上浮、无需重新平衡。这两条定理解释了 Splay 在 skew 工作负载下的优越性。

两条定理是 Splay 理论核心：静态最优性保证"不差于任何静态最优树"，工作集定理说明"访问局部性越好、代价越低"。工程上它们支撑 Splay 在自适应/缓存场景的应用。理解"动态自调整接近最优"是关键。

• 势能 Φ = Σ log(size(x))，size 为子树大小
• zig/zig-zig/zig-zag 三种旋转的均摊代价分析
• 推导 splay 摊还 O(log n)

Sleator-Tarjan 用势能法分析 splay：定义势能 Φ(T) = Σ log(size(x))（所有节点子树大小取对数之和）。单次 splay 的摊还代价 = 实际旋转的代价 + 势能变化。对三种旋转分别分析：zig（单旋）摊还代价 O(1 + log(size(newroot)) - log(size(x)))；zig-zig（双旋，父与子同侧）摊还代价 O(3(log(size(newroot)) - log(size(x))))；zig-zag（双旋，父与子异侧）摊还代价 O(3(log(size(newroot)) - log(size(x))))。关键推导：双旋时通过"对称性"证明两次旋转后势能变化约等于 3Δlog(size)，抵消旋转的常数代价；把单次 splay 的多次旋转累加，中间项互相抵消，最终摊还代价 O(log n)(从根到 x 的深度对数)。因此 splay 每次操作 O(log n) 摊还。

推导的核心是"用势能变化抵消旋转代价"。zig-zig/zig-zag 的势能变化被证明足以支付旋转本身，剩余只有 O(log n) 的深度差。累加时中间势能项抵消。理解"势能补偿旋转"是推导的精髓。

• LCT 维护链（preferred path），是 Top Tree 的特例
• Top Tree 用簇抽象，覆盖任意连通子图
• 簇抽象扩展到动态子树、动态最小割等

Top Tree 与 LCT 都是动态树数据结构，但抽象层次不同：LCT 用"实链剖分 + splay"，只维护路径（链）信息；Top Tree 用"簇（cluster）"抽象，每个簇是任意连通子图（最多 2 个边界节点），通过 Rake/Compress 合并簇。LCT 可以看作 Top Tree 在"每条链一个簇"下的特例。簇抽象更一般，因此 Top Tree 能扩展到更复杂的动态树问题：动态子树（子树聚合）、动态路径+子树混合、动态最小割/连通性、动态树上的 DP 等。Top Tree 的代价是实现更复杂（簇的合并、边界节点维护、Splay 拓扑树），但表达能力更强。工程上，LCT 适合纯路径问题，Top Tree 适合需要子树/更复杂结构的动态树问题。

关系是"LCT 是 Top Tree 的特例（链抽象），Top Tree 用簇抽象推广到任意连通子图"。簇抽象的价值是更强的表达能力，代价是复杂度。理解"链 vs 簇"的抽象层次差异是关键。

• link(x,y)：makeroot(x) 后确认 x,y 不同树，再连边
• cut(x,y)：makeroot(x) + access(y) 后确认 x 是 y 的父，再断开
• 错误操作破坏虚实结构与聚合

LCT 的 link 与 cut 有严格前置条件。link(x,y)：先 makeroot(x)，再确认 x 与 y 不在同一棵树（若已连通则连边会成环，破坏"森林"性质），确认后才把 x 的父指针指向 y 完成连边。cut(x,y)：先 makeroot(x)、access(y)、splay(y)，此时 x 是 y 的左子树根（路径上 x 是 y 的父），需确认 x 确实是 y 的直接父（x 的右子为空），再断开 x 与 y 的边。错误操作会破坏结构：link 已成环的节点会违反树的性质、导致虚实划分与聚合错误；cut 不存在的边或父子关系错误会误删正确的边、破坏树结构。正确使用前置条件保证 LCT 的树形不变式（每个节点至多一个父、无环）与聚合正确性。

前置条件是"树形不变式"的保证：link 需无环（不同树），cut 需存在且正确的父子关系。错误操作破坏不变式会让 LCT 的 splay/虚实划分错乱。理解"操作前验证不变式"是正确使用 LCT 的关键。