可持久化平衡树

What · 是什么

可持久化平衡树在 OI 中最常用的是可持久化无旋转 Treap（FHQ Treap）：利用其 Split/Merge 过程只修改路径上节点、且天然适合『复制沿途节点（path copying）』的特点，把每个操作（插入/删除/查询）都作用在某个历史版本上并产生新版本。因无旋转、无指针改动旧版本，Split/Merge 中每次新建节点即可保留全部历史。支持任意历史版本的插入/删除/求排名/求 k 小/前驱/后继。经典模板：Luogu P3835（可持久化平衡树）、P3919（可持久化数组）、P5055（可持久化文艺平衡树）。

Why · 为什么

How · 实现

伪代码

split(x, k):            # 返回 (<k 的树, >=k 的树)；路径节点全部新建
  if x 为空: return (0, 0)
  nw = 复制节点 x
  if val[x] < k:
    a, b = split(r[x], k)
    r[nw] = a; pull(nw); return (nw, b)
  else:
    a, b = split(l[x], k)
    l[nw] = b; pull(nw); return (a, nw)
merge(a, b):             # 按 prio 合并；被改儿子指针的节点要复制
  if a 空: return b
  if b 空: return a
  if prio[a] < prio[b]: nw=复制a; r[nw]=merge(r[a], b); pull(nw); return nw
  else:                  nw=复制b; l[nw]=merge(a, l[b]); pull(nw); return nw
insert(ver, k): a,b=split(root[ver],k); return merge(merge(a,newnode(k)),b)
erase(ver, k):  a,b=split(root[ver],k); c,d=split(b,k+1); return merge(a,merge(l[c],d))

Python 实现

import random


class PersistentTreap:
    """可持久化无旋转 Treap（FHQ）。支持基于任意历史版本做插入/删除/排名/k小/前驱/后继。
    所有数组 0 号均为空节点哨兵。ver 从 0 开始（空树）。"""

    def __init__(self):
        self.l = [0]; self.r = [0]; self.key = [0]
        self.prio = [0]; self.size = [0]
        self.vers = [0]

    def _newnode(self, k):
        idx = len(self.key)
        self.l.append(0); self.r.append(0); self.key.append(k)
        self.prio.append(random.random()); self.size.append(1)
        return idx

    def _pull(self, x):
        self.size[x] = self.size[self.l[x]] + self.size[self.r[x]] + 1

    def _split(self, x, k):
        """返回 (a, b): a 的键全部 < k, b 的键全部 >= k。路径节点新建。"""
        if x == 0:
            return 0, 0
        if self.key[x] < k:
            a, b = self._split(self.r[x], k)
            nw = self._newnode(self.key[x])
            self.l[nw] = self.l[x]; self.r[nw] = a
            self._pull(nw)
            return nw, b
        else:
            a, b = self._split(self.l[x], k)
            nw = self._newnode(self.key[x])
            self.l[nw] = b; self.r[nw] = self.r[x]
            self._pull(nw)
            return a, nw

    def _merge(self, a, b):
        if a == 0:
            return b
        if b == 0:
            return a
        if self.prio[a] < self.prio[b]:
            nw = self._newnode(self.key[a])
            self.l[nw] = self.l[a]; self.r[nw] = self._merge(self.r[a], b)
            self._pull(nw)
            return nw
        else:
            nw = self._newnode(self.key[b])
            self.r[nw] = self.r[b]; self.l[nw] = self._merge(a, self.l[b])
            self._pull(nw)
            return nw

    def insert(self, ver, k):
        a, b = self._split(self.vers[ver], k)
        root = self._merge(self._merge(a, self._newnode(k)), b)
        self.vers.append(root)
        return root

    def erase(self, ver, k):
        a, b = self._split(self.vers[ver], k)
        c, d = self._split(b, k + 1)
        if c:
            c = self._merge(self.l[c], self.r[c])
        root = self._merge(a, self._merge(c, d))
        self.vers.append(root)
        return root

    def rank(self, ver, k):
        """返回 < k 的元素个数 + 1"""
        x = self.vers[ver]; r = 0
        while x:
            if self.key[x] < k:
                r += self.size[self.l[x]] + 1
                x = self.r[x]
            else:
                x = self.l[x]
        return r + 1

    def kth(self, ver, k):
        x = self.vers[ver]
        while True:
            lsz = self.size[self.l[x]]
            if k <= lsz:
                x = self.l[x]
            elif k == lsz + 1:
                return self.key[x]
            else:
                k -= lsz + 1
                x = self.r[x]

    def pred(self, ver, k):
        r = self.rank(ver, k)
        return self.kth(ver, r - 1) if r >= 2 else None

    def succ(self, ver, k):
        r = self.rank(ver, k + 1)
        return self.kth(ver, r) if r <= self.size[self.vers[ver]] else None


if __name__ == '__main__':
    random.seed(23)
    pt = PersistentTreap()
    hist = [[]]  # hist[v] = 第 v 个版本的已排序元素列表（暴力参照）
    for step in range(300):
        cur = hist[-1]
        if not cur or random.random() < 0.6:
            k = random.randint(1, 15)
            pt.insert(len(hist) - 1, k)
            nv = sorted(cur + [k])
        else:
            k = random.choice(cur)
            pt.erase(len(hist) - 1, k)
            nv = list(cur); nv.remove(k)
        hist.append(nv)
    # 验证所有历史版本均正确且互不影响
    for vv in range(len(hist)):
        lst = hist[vv]
        for k in range(1, 16):
            assert pt.rank(vv, k) == 1 + sum(1 for x in lst if x < k), (vv, k)
        for idx in range(1, len(lst) + 1):
            assert pt.kth(vv, idx) == lst[idx - 1], (vv, idx)
        # 前驱=小于 k 的最大值；后继=大于 k 的最小值（严格）
        for k in range(1, 16):
            smallers = [x for x in lst if x < k]
            assert pt.pred(vv, k) == (smallers[-1] if smallers else None), (vv, k)
            biggers = [x for x in lst if x > k]
            assert pt.succ(vv, k) == (biggers[0] if biggers else None), (vv, k)
    print('persistent-balanced: All tests passed.')

易错点

• split/merge 中必须『先复制节点再修改』，直接改原节点会破坏旧版本
• 复制节点时左右儿子指针要带过来（拷贝旧值），漏拷贝导致新版本缺子树
• 版本索引：insert/erase 各产生一个新版本（append 一次根），查询不 append；P3835 的版本编号=操作序号
• merge 后要 pull(size) 更新，遗忘会破坏 kth/rank
• delete 语义：split(b,k+1) 取恰等于 k 的中段，多键时只删一个；写成 split by k 边界错
• prio 比较方向与 merge 分支写反会破坏堆性质（小根堆 prio 在上）

例题

信源

• OI Wiki✓ https://oi-wiki.org/ds/persistent-balanced/
• OI Wiki✓ https://raw.githubusercontent.com/OI-wiki/OI-wiki/master/docs/ds/persistent-balanced.md
• 书籍✓ 范浩强《范浩强谈数据结构》（无旋 Treap）