RRB-Tree 与 Splay 操作

• 隐式下标：以子树大小代替键值
• split/merge 实现区间操作
• 懒标记翻转与下推

隐式 Treap 以"子树大小"作为隐式键值：节点不存键，而是用子树节点数表示其覆盖的位置范围。split(根, k) 把前 k 个元素与剩余元素分裂成两棵，merge 按随机优先级合并两棵。插入：先把序列分成前 x 个和后，再在中间 merge 新节点；删除：split 出目标区间后直接丢弃；翻转：split 出区间后给该子树打懒标记，再 merge 回。由于每操作只沿树高 O(log n) 的路径，复杂度均为 O(log n)。这使隐式 Treap 能高效维护括号序列合法性（用前缀和最小值）与文本编辑器的任意位置编辑。

隐式 Treap 的关键是用"位置"而非"值"作为访问依据，因此天然适合序列的区间操作。随机优先级保证期望平衡，无需旋转就能实现分裂合并，配合懒标记可处理翻转。括号序列维护时在节点上维护区间和、最小前缀和，翻转通过懒标记切换，合并时 O(1) 合并信息。

• 节点左右孩子与父指针
• 旋转时指针重连的 O(1) 步骤
• 父子关系更新

Splay 的旋转（zig 单旋）针对节点 x 和其父 p：把 x 的某一子树（视方向）接到 p 上，把 p 变成 x 的孩子，同时更新三者的 parent 指针与 x 新的父节点。整个过程只改动 O(1) 个指针，故单次旋转 O(1)。zig-zig 是先旋转父节点再旋转 x，zig-zag 是先旋转 x 再旋转 x（两次单旋），两者都是 O(1) 次旋转的组合。实现时用数组 node[] 存左右孩子与父指针，旋转后维护子树 size 等聚合信息。

旋转是 Splay 一切操作的基础，指针重连必须保证"父子关系"与"聚合信息"一致。看似简单，但工程上易错点在于：p 是新父节点时，p 在祖父中的位置要更新；以及旋转后要自底向上更新 size。双向链表式的指针模型让 rotate 成为可复用的原子操作。

• 每个节点保存多个版本字段（fat node）
• 版本号索引与查找
• 与路径复制（Path Copying）的空间/时间对比

FAT Node 方法让每个节点存储一个"字段多版本"的数组：每个字段可被多次写入，每次写入记录版本号与值。节点被修改时不在树上新建节点，而是把新值追加到该节点的字段版本列表里，通过版本号二分查找任意历史值。这样无需复制整条路径，写入 O(1)。代价是节点内部字段可能变多，查询需在版本列表上二分，且所有历史共享节点会让"当前版本"的访问路径变长。它比路径复制更省空间（不复制整条路径），但实现复杂、常数大，多用于理论（如部分可持久化）。

FAT Node 与路径复制是持久化的两种主流策略：路径复制"复制路径、共享子树"，FAT Node"原地积累版本、节点内版本化"。FAT Node 每次修改 O(1) 空间但查询需处理版本，路径复制单次 O(log n) 空间但查询干净。工程上偏好路径复制（结构简单、缓存友好），FAT Node 更多用于结构化逆向或理论。

• 只复制被修改路径上的节点
• 未修改子树与旧版本共享
• 节点共享与空间复用

路径复制指：更新时从根到被修改位置复制这条路径上的节点，复制出的新节点指向未修改的子树（与旧版本共享），而修改位置被替换为新值。这样新版本与旧版本共享所有未变化的子树，每个被复制节点 O(1) 地"复用"旧子树指针。由于树高 O(log n)，单次更新只新建 O(log n) 个节点，其余 O(n) 个节点全部共享。节点共享正是持久化结构空间可控的核心——它让"复制"的成本从整棵树降到一条路径。

"O(1) 节点共享"指每个未修改子树只需一个指针被新节点引用，无需复制其内容。路径复制把"全量复制"转化为"路径复制 + 子树共享"，是线段树、主席树、函数式数据结构共享的底层机制。它与节点不可变（immutable）相辅相成：正因为节点不可变，才能被安全地多版本共享。

• Splay 对固定访问序列的均摊最优性
• 访问序列的静态最优性质
• 与静态最优二叉搜索树的对比

Sleator-Tarjan 静态最优性定理指出：对于任意固定的访问序列，Splay 树（无需任何预处理）的访问代价与已知最优的静态二叉搜索树（BST）的代价同阶（都是 O(log n) 每个访问的摊还），且 Splay 的摊还复杂度不超过任何静态 BST 的复杂度乘以常数。这意味着 Splay 不需要知道访问分布就能自适应地达到接近最优。工程意义在于：Splay 是"自调整"数据结构，把最近访问的元素通过 splay 移到根，利用时间局部性优化，适用于访问分布未知但存在偏斜的场景（如缓存、访问频率高的元素）。

静态最优性说明了 Splay 的自适应能力：即使访问序列有强偏斜（部分元素高频访问），Splay 也能达到与最优静态 BST 相近的代价，无需额外信息。相比静态最优 BST 需要预先知道频率，Splay 完全在线。这是 Splay 的重要理论优势，也是它"访问即旋转"合理性的依据。

• RRB-Tree 的 radix 树结构 + 重平衡
• concat 的节点整合与 relabel
• Clojure PersistentVector 的 tail 优化

RRB-Tree（Relaxed Radix Balanced Tree）是 Clojure PersistentVector 的扩展，把 radix 树从"满叉"放宽为"可部分填充"，允许节点在容量范围内（如 M/2 到 M）变化，从而支持 O(log n) 的 concat：把两棵树的深路径节点重新整合（relabel/重平衡），无需逐元素复制。append 也因 relax 而更快。Clojure PersistentVector 用分支因子 32 的 radix 树 + 一个独立 tail 数组：append 先写 tail，tail 满才推入树，因此绝大多数 append 是 O(1)（摊还），但 concat 需要 O(n) 或 O(log n) 视实现。RRB-Tree 在 PersistentVector 基础上加入 relax，使 concat 也达到 O(log n)。

普通 radix 树（满叉）concat 时必须把右树节点逐层插入，代价高；RRB-Tree 允许节点部分填充，可用"整层整合"把两棵树在 O(log n) 内合并，再对不满节点重平衡。tail 优化是 PersistentVector 对 append 的加速，但不解决 concat。RRB-Tree 的价值在于同时优化 append 与 concat，是函数式数据结构的经典工程成果。

• radix 树的分支因子与深度
• concat 时整层节点整合避免逐元素复制
• 重平衡（rebalancing）处理不满节点

RRB-Tree 的 concat 是递归的：比较两棵树的根深度，把浅树的根与深树的对应层节点"整合"，能合并的节点就地合并（同一层多个节点合成一个满节点），不满的节点通过重平衡（relabel）调整。由于 radix 树分支因子 M（如 32）固定，树高 O(log_M n)，递归整合只在 O(log n) 层上进行，每层处理 O(1) 个节点，因此 concat 是 O(log n)。关键是"整层整合"而非逐元素搬运：一个节点可容纳 M 个元素，合并满节点时只需指针操作，避免了把右树每个元素重新插入左树的 O(n) 成本。

逐元素复制 O(n) 的根源是平凡地把一棵树的每个元素 append 到另一棵；RRB-Tree 通过"按层打包"把 O(n) 个元素一次性装进 O(log n) 个节点，再在层间重平衡。重平衡保证节点容量在 [M/2, M]，从而维持树高与 O(log n) 的复杂度。这是 RRB-Tree 相对朴素持久化向量的核心优势。

• 双旋 vs 单旋的势能差异
• 深层节点访问时双旋的减势效果
• 单旋的退化反例

双旋（zig-zig 先旋父再旋子，zig-zag 旋两次子）能显著降低被访问节点所在路径的深度，从而在势能分析中产生足够的势能释放，摊还 O(log n)。单旋（每次只把访问节点旋转到父位置）虽每次 O(1)，但存在访问序列使整棵树退化为一条链（如反复访问最深层节点，每次只上移一层，很久才到根，且树形依然糟糕），摊还退化为 O(n)。双旋的"父子一起转"让深层节点每次上移两层，且每次旋转把子树深度减半，势能下降足够补偿，保证摊还界。

势能函数 Φ = Σ log(size(x))（子树大小对数）。双旋中 zig-zig 的势能变化可证明为 ≤ 3(log s'(x) − log s(x))，从而总摊还代价 O(log n)。单旋只让节点上移一层，势能未能充分释放，存在"反复访问深层节点使树变链"的反例，导致摊还 O(n)。双旋是 Splay 均摊性能的关键设计。

• 哨兵（-inf/+inf）节点的作用
• split 出区间、懒标记、merge 回
• 区间翻转/插入/删除的统一流程

Splay 区间操作常用带两个哨兵节点的树（下标 0 处和最右端各加一个哨兵），方便定位区间边界。区间 [l,r] 的操作：先把第 l 个节点 splay 到根，再把第 r+2 个节点 splay 到根的右孩子，则根的右孩子的左子树恰好是 [l,r] 区间。翻转：对该子树打懒标记；删除：直接摘掉该子树；插入：把新序列作为该子树的一部分 merge 回。定位第 k 个节点用子树大小 + splay 到根的经典两步。所有操作 O(log n) 摊还。

哨兵节点消除了边界特判，使 [l,r] 的定位转化为"两次 splay 到根"的统一模式。懒标记下推保证区间翻转正确反映到子树。这套"split 出区间 → 打标记/修改 → 合并回"的框架是 Splay 区间操作、文艺平衡树（区间翻转）与 LCT 路径操作的共同基础。

• Treap 的随机优先级 + 堆性质实现期望平衡
• Splay 的访问即旋转 + 局部性
• 期望 vs 均摊两种平衡保障

Treap 为每个节点随机分配优先级，树按 BST 键序 + 堆优先级构造，随机优先级使树高以高概率为 O(log n)，这是"期望平衡"——依赖随机性，但无需访问信息。Splay 不依赖随机性，而是每次访问后把节点旋转到根，使最近访问的元素位于树顶，利用"时间局部性"（被访问的元素很可能再次被访问），通过势能分析保证任意访问序列摊还 O(log n)，这是"均摊平衡"。区别：Treap 的平衡是概率性的、与访问无关；Splay 的平衡是确定性的摊还、与访问模式相关。

Treap 用随机化把"平均树高 O(log n)"概率化；Splay 用"访问即旋转"把低频/最近访问元素移到顶部，从而对偏斜访问序列也高效。两者都能达到 O(log n) 的平衡，但 Treap 更简单、可持久化友好，Splay 对访问局部性适应更好。工程上 Treap 用于无旋随机平衡，Splay 用于需要区间操作与局部性优势的场景。

• 不可变数据结构 + 路径复制
• 共享结构、无副作用
• 在函数式语言（如 Clojure/Haskell）中的应用

函数式编程强调不可变性（immutability）与无副作用。路径复制让不可变数据结构支持"修改"：不破坏原结构，而是复制从根到修改点的路径，生成新版本，未修改部分与原版本共享。这样"修改"返回新结构而原结构不变，天然满足引用透明与纯函数语义。如 Clojure 的 PersistentVector、Haskell 的持久化平衡树、不可变 Map 都基于路径复制 + 子结构共享，实现"看起来可修改、实际不可变"的高效结构，作为函数式集合的底层实现。

路径复制把"不可变"与"高效更新"这对矛盾统一起来：更新不破坏原对象，但通过共享避免全量复制。它让函数式语言能安全地在并发/递归中共享数据而无需锁或深拷贝，是函数式数据结构（persistent data structures）的基石，也是函数式语言 STM、纯函数算法的基础。

• split 用两次 splay 定位区间
• 翻转打懒标记
• merge 重新拼接

Splay 的 split 与 merge 通常借由"splay 到根"实现。split(树, k)：把第 k 个节点 splay 到根，则其左子树为前 k−1 个、右子树为剩余，左右即分裂成两棵。翻转区间 [l,r]：先 split 出 [l,r] 子树，对其打懒标记（交换左右孩子语义），再 merge 回。merge(两棵)：把左树的最大节点 splay 到根，其右孩子为空，接上右树即可。工程上每次操作前先下推根的懒标记，保证子树结构正确。所有操作 O(log n) 摊还。

Splay 的 split/merge 依赖"把某个节点 splay 到根"来分离区间，配合懒标记实现翻转。与 FHQ Treap 的 split/merge 不同，Splay 需要旋转，但同样能实现区间分裂合并。工程上常封装成"区间操作三件套"：splay 定位 → 修改 → 合并。

• 懒标记的语义与祖先链
• 先下推祖先再操作子树的原因
• 通用模板的 pushdown 顺序

懒标记（如翻转标记）会"延迟"反映到子树，但在访问某个节点或其子树时，必须先把从根到该节点路径上的所有懒标记下推，否则该节点看到的子树信息是"未翻转"的错误状态。因此当 splay 把某个节点转到根时，应先从上到下把祖先链上的标记逐层 pushdown，再对目标子树做修改，保证修改基于正确的结构。文艺平衡树模板中，splay 前先收集路径上所有节点并逆序下推标记，再进行目标 splay 与操作。

懒标记如果不下推就操作子树，会读到过期/未翻转的聚合值，导致错误。正确顺序是"先下推祖先标记 → 再翻转/修改 → 再上推更新聚合"。下推必须自上而下（从根到叶），因为祖先标记会影响到后代。工程上用一个栈收集路径节点，从根到目标逆序 pushdown，保证顺序正确。

• 势能函数 Φ = Σ log(size)
• 三种旋转情况的势能变化
• 摊还代价 = 实际代价 + 势能变化

设势能 Φ = Σ_log size(x)，splay 时被访问节点 x 从深层上移到根。对 zig-zig/zig-zag，设旋转前后节点 x 的子树大小由 s(x) 变为 s'(x)=s(根)。每一步旋转的摊还代价（实际代价 1 + 势能变化）可以证明 ≤ 3(log s'(x) − log s(x))。对 zig-zig 与 zig-zag 分别逐项计算：zig-zig 涉及 x、父 p、祖父 g 三个点的 size 变化，利用对数和不等式 log s'(x)·log s'(p) 等可消去中间项，得到 3(log s'(x) − log s(x))；zig-zag 同理。最后一步 zig（直接到根）额外 O(1)。把每一步相加，中间项对消，最终总摊还代价 ≤ 3 log(n) + O(1) = O(log n)。

势能法证明的关键是"每一步双旋的摊还代价能被 3(log s'(x)−log s(x)) 控制"，且这些增量沿路径求和时首尾相消，只剩 x 到根的 size 对数值变化（≤ log n）。这正说明双旋为何必须：只有双旋才能让中间项对消，单旋无法得到该界。推导细节在于对 zig-zig 用 log 的凸性/对数不等式消去 p、g 的项。

• 势能函数
• zig-zig 与 zig-zag 的势能变化上界
• 总摊还代价的推导

势能 Φ=Σ log s(x)。对 zig-zig：设 x 经旋转后子树大小变为 s'，rotation 的实际代价为 1，势能变化 ΔΦ = (log s'(x)+log s'(p)+log s'(g)) − (log s(x)+log s(p)+log s(g))。由于旋转后 s(x)=s'(g)（x 上升到 g 的位置），且 s'(p) ≤ s'(x)，可推得 ΔΦ ≤ 3(log s'(x) − log s(x))。对 zig-zag 类似，可证明同界。因此每次双旋摊还 ≤ 1 + ΔΦ ≤ 3(log s'(x) − log s(x))。splay 过程中沿路径的这些增量求和，中间项对消，最终总摊还 ≤ 3 log n + O(1) = O(log n)。这证明任意 m 次 splay 总代价 O(m log n + n log n)。

证明的灵魂是"每次双旋的摊还代价正比于 x 子树大小的对数增量"，而路径上这些增量接力式地由 x 传向根，最终以 O(log n) 封顶。zig-zig 与 zig-zag 两种旋转分别验证该上界成立，从而无需关心具体访问序列，得到总体摊还 O(log n)。这也解释了"为什么必须双旋"。

• RRB-Tree 的树结构 vs Immutable.js 的哈希 trie/数组 trie
• 结构共享的粒度
• 缓存局部性与分支因子

RRB-Tree 是分支因子 32 的 radix 树（可放宽），适合序列/向量的顺序访问与 concat，结构共享粒度为"节点"，节点内连续，缓存局部性较好。Immutable.js 的 List/Map 底层常用哈希数组映射 trie（HAMT）或分支因子 32 的数组 trie，结构共享类似，但面向"键值/列表"泛型操作，且为了兼容 JS 对象，常有额外装箱与哈希计算开销。缓存局部性上，两者都因分支因子 32 使节点能放入缓存行，但 RRB-Tree 的节点是连续数组、顺序访问更友好；Immutable.js 因通用性牺牲部分紧密性。结构共享（两者都 O(log n) 更新）保证了不可变集合的高效更新。

两者都是"不可变 + 结构共享"的 radix trie 实现，核心差异在应用场景与工程细节：RRB-Tree 专为序列优化（concat、顺序遍历），Immutable.js 面向通用 JS 集合（动态键、哈希层）。分支因子 32 是缓存友好与深度折中的经典选择。面试关注结构共享原理与局部性差异。

• 普通持久化向量 concat 的 O(n) 劣势
• RRB-Tree 的 O(log n) concat
• 工程应用价值

普通持久化向量（如 Clojure PersistentVector）append 是摊还 O(1)（tail 优化），但 concat（拼接两个大向量）需要把右向量逐元素 append 到左向量，最坏 O(n+m)。RRB-Tree 通过"允许节点部分填充 + 重平衡"把 concat 优化到 O(log(n+m))，因此适合需要大量拼接不可变序列的场景（如文本编辑、操作日志合并、函数式区间运算）。工程价值在于：在保持持久化向量 O(log n) 访问与共享优势的同时，补齐了 concat 的短板，使不可变序列成为"全操作均衡"的通用结构。

concat 是序列操作的重要一环，普通向量因满叉 radix 树无法高效拼接而退化。RRB-Tree 的 relax 让节点可部分填充，从而在拼接时整层打包、重平衡，复杂度从 O(n) 降到 O(log n)。这是 RRB-Tree 相对普通持久化向量最核心的工程优势。