可持久化 Trie

What · 是什么

可持久化 Trie（Persistent Trie）是可持久化思想在 Trie 上的应用：每次插入一个数/串时，沿插入路径复制新节点、复用未改动的子树，保存每个版本的根，从而支持『任意历史版本』的查询。竞赛中最常见的是可持久化 01-Trie：维护每个前缀插入数的二进制位统计，支持『在区间 [l,r] 中选一个数 x 与给定值异或的最大值』——用两版根差分出区间内的计数，贪心走与 x 相反位（有则走）。经典例题：Luogu P4735 最大异或和（维护可持久化前缀异或和）。

Why · 为什么

How · 实现

伪代码

ch[cur][2], cnt[cur]; roots=[0]
insert(prev_root, x):
  new_root = 拷贝 prev_root 的根并 cnt+1
  node = prev_root; cur = new_root
  for b in 30..0:
    bit = (x>>b)&1
    old_child = ch[node][bit]
    新建节点拷贝 old_child 的 ch 与 cnt，cnt+1
    ch[cur][bit] = 新节点
    node = old_child; cur = 新节点
  roots.append(new_root)
query(l, r, x):   # [l,r] 内与 x 异或最大
  u = roots[l-1]; v = roots[r]; ans = 0
  for b in 30..0:
    bit = (x>>b)&1; want = bit^1
    if cnt[ch[v][want]] - cnt[ch[u][want]] > 0:
      ans |= 1<<b; u = ch[u][want]; v = ch[v][want]
    else:
      u = ch[u][bit]; v = ch[v][bit]
  return ans

Python 实现

class PersistentTrie:
    """可持久化 01-Trie：支持前缀版本与区间异或最大值查询。
    用法: pt = PersistentTrie(B); 对每个 x 调 pt.add(x);
    pt.max_xor_in(l, r, x) 返回 max_{i in [l,r]}(arr[i] ^ x)。"""

    def __init__(self, B=30):
        self.B = B
        self.ch = [[0, 0]]
        self.cnt = [0]
        self.roots = [0]

    def add(self, x):
        old = self.roots[-1]
        new_root = len(self.ch)
        self.ch.append([self.ch[old][0], self.ch[old][1]])
        self.cnt.append(self.cnt[old] + 1)
        cur, node = new_root, old
        for b in range(self.B, -1, -1):
            bit = (x >> b) & 1
            old_child = self.ch[node][bit]
            nxt = len(self.ch)
            self.ch.append([self.ch[old_child][0], self.ch[old_child][1]])
            self.cnt.append(self.cnt[old_child] + 1)
            self.ch[cur][bit] = nxt
            cur, node = nxt, old_child
        self.roots.append(new_root)
        return new_root

    def max_xor_in(self, l, r, x):
        """区间 [l,r]（1 索引含端点，按插入顺序）内与 x 异或的最大值"""
        u, v = self.roots[l - 1], self.roots[r]
        ans = 0
        for b in range(self.B, -1, -1):
            bit = (x >> b) & 1
            want = bit ^ 1
            c = self.cnt[self.ch[v][want]] - self.cnt[self.ch[u][want]]
            if c > 0:
                ans |= 1 << b
                u = self.ch[u][want]
                v = self.ch[v][want]
            else:
                u = self.ch[u][bit]
                v = self.ch[v][bit]
        return ans


if __name__ == '__main__':
    import random

    def brute(arr, l, r, x):
        return max(x ^ v for v in arr[l - 1:r])

    arr = [1, 2, 3, 4, 5]
    pt = PersistentTrie(4)
    for x in arr:
        pt.add(x)
    assert pt.max_xor_in(1, 5, 0) == 5 ^ 0  # 5
    assert pt.max_xor_in(2, 4, 3) == brute(arr, 2, 4, 3)

    random.seed(22)
    for _ in range(300):
        B = 4
        pt = PersistentTrie(B)
        n = random.randint(1, 12)
        arr = [random.randint(0, 31) for _ in range(n)]
        for x in arr:
            pt.add(x)
        for _ in range(20):
            l = random.randint(1, n)
            r = random.randint(l, n)
            x = random.randint(0, 31)
            assert pt.max_xor_in(l, r, x) == brute(arr, l, r, x), (l, r, x, arr)
    print('persistent-trie: All tests passed.')

易错点

• 插入时新节点必须完整拷贝旧儿子路径（ch 与 cnt），漏拷贝 cnt 会让计数错误
• 查询差分 u=roots[l-1]、v=roots[r] 写错索引导致区间错
• 贪心选择相反位时若 cnt 差为 0 必须退回同向位，不能跳过该位
• 前缀异或和的区间转换（P4735 中 [l,r] 下标要对应到 s[l-1..r-1]）容易差一
• B 位选择不足（如值域 2^31 却用 B=30 少一位）导致高位丢失
• ch 数组初始化 [0,0] 指向节点 0（空节点），cnt[0]=0 必须保证 0 号节点计数为 0

例题

信源

• OI Wiki✓ https://oi-wiki.org/ds/persistent-trie/
• OI Wiki✓ https://raw.githubusercontent.com/OI-wiki/OI-wiki/master/docs/ds/persistent-trie.md