可持久化 Trie 是什么？它适合解决什么问题？
简化版
可持久化 Trie 是一种保留历史版本的 Trie。
每次插入或更新时，不直接修改旧节点，而是复制路径上的节点，新版本共享未变化的部分。这样可以同时查询多个历史版本。
它常用于区间异或最大值、历史版本词典、离线查询等问题。核心思想是结构共享，不是完整复制整棵树。
详细版
普通 Trie 只有当前状态。可持久化 Trie 会为每次操作生成一个新 root。
插入一个新值时：
newRoot = clone(oldRoot)
沿插入路径克隆节点
未变化子树直接共享| 做法 | 空间 |
|---|---|
| 每个版本完整复制 | 很大 |
| 路径复制 + 共享子树 | 每次只增加 O(L) 节点 |
其中 L 是 key 的长度。对于 0-1 Trie，L 可能是 31 或 32。
完整版教学
1. 什么叫可持久化
可持久化数据结构不是指写到磁盘，而是指保留历史版本。
对 Trie 来说，插入新 key 后，旧版本仍然可以查询，新版本也可以查询。
例如：
root0: 空 Trie
root1: 插入 5
root2: 插入 8查询 root1 时，只能看到 5；查询 root2 时，可以看到 5 和 8。
2. 为什么不能完整复制
如果每次操作都复制整棵 Trie，空间会爆炸。
假设已有 100000 个节点，做 100000 次插入，完整复制会非常夸张。
可持久化的关键是：只复制变化路径，其他节点共享。
可持久化 Trie 的灵魂是路径复制和结构共享。
3. 插入时复制哪些节点
插入一个长度为 L 的 key，只会影响从 root 到叶子的这条路径。
所以只需要：
- 创建新 root；
- 每走一层复制当前节点；
- 修改复制节点的孩子指针；
- 未走到的其他孩子继续指向旧节点。
这样一次插入新增节点数是 O(L)。
4. 0-1 Trie 中为什么常见
可持久化 Trie 经常和二进制 Trie 结合，用来处理异或问题。
每个整数看成 31 位或 32 位二进制串。插入一个数只增加大约 32 个节点，空间可控。
insert(versionRoot, x):
for bit from high to low:
clone node
count++节点上常维护 count，表示该版本下有多少数字经过这里。
5. 区间查询怎么做
可持久化 Trie 的经典用法是区间 [l, r] 查询。
如果 root[i] 表示前 i 个数构成的 Trie，那么区间 [l, r] 的信息可以通过：
root[r] - root[l - 1]来得到。
节点计数相减，就知道某个分支在区间内是否存在数字。
6. 查询最大异或的思路
要找和 x 异或最大的数，通常从高位到低位贪心。
如果当前位是 0，优先找 1；如果当前位是 1，优先找 0。
在区间版本中，要判断目标分支是否存在，需要比较两个版本的计数差：
countRightBranch = nodeR.child[want].count - nodeL.child[want].count如果大于 0，说明区间里存在这个分支。
7. 和普通 Trie 的区别
| 维度 | 普通 Trie | 可持久化 Trie |
|---|---|---|
| 版本 | 只有当前版本 | 多个历史版本 |
| 更新方式 | 原地修改 | 路径复制 |
| 空间 | 较省 | 每次新增 O(L) |
| 查询 | 当前数据 | 任意版本或区间 |
可持久化 Trie 更强，但实现和空间管理也更复杂。
8. 常见误区与追问
- 误区：可持久化就是把 Trie 保存到文件。 这里指保留历史版本，不是磁盘持久化。
- 误区：每次更新要复制整棵树。 只复制更新路径，未变化子树共享。
- 误区：可持久化 Trie 只适合字符串。 0-1 Trie 处理整数二进制位更常见。
- 追问：为什么每次新增节点是
O(L)？ 因为只复制从 root 到 key 末尾的一条路径。 - 追问：区间查询为什么能用两个版本相减？ 前缀版本包含前缀集合，
root[r] - root[l-1]就留下区间贡献。