CC++ & Algorithm

可持久化Trie简介

极难2
语言版本：通用
概述：可持久化Trie允许我们访问插入任意个单词后字典树的历史版本，解决需要查询“在某个时间点之前”或“第i次插入前”等前缀信息的问题。

可持久化Trie：让字典树拥有“时光机”

你有没有想过，如果你的单词本可以像游戏存档一样，随时回到任意一天查看当时的单词列表，那该多方便？普通字典树只能看到最新状态，而可持久化Trie（Persistent Trie）就是字典树的“时光机”——它保存了每一次插入后的历史版本，让你能随时查询“在第5次插入之前”或“第i个版本”的字典树信息。

可持久化Trie的核心思想是：每次插入时，只复制路径上的节点，其他节点与旧版本共享。这样，你既拥有了所有历史版本，又不会浪费太多空间。它常用于解决历史前缀查询、区间异或极值等问题，是数据结构和算法竞赛中非常有用的工具。

为什么需要可持久化？—— 生活中的例子

? 单词本的“差异备份”

假设你有一本单词本（字典树）。每天你都会添加几个新单词，比如：

  • 周一：cat, dog
  • 周二：bird, car
  • 周三：apple, cat（重复添加也没关系）

你想知道“周二之前”单词本里有哪些词，或者“周一之后、周三之前”有哪些词。如果每天把整个单词本复印一份，那就太浪费纸了。聪明的方法是：每次添加时，只记录变化的部分，其他部分直接沿用旧版本。这就是可持久化的核心——共享已有节点，只复制修改路径。

? 游戏中的“存档机制”

玩RPG游戏时，你会在不同关卡保存多个存档。每个存档只记录从上一个存档以来的差异（比如等级、道具），而不是整个游戏数据。可持久化Trie就像这些存档，每次插入（存档）后，你都能通过对应的“根节点”进出那个时间点的字典树。

可持久化Trie的核心原理

1. 节点复制 vs 节点修改

普通字典树插入时，会沿着路径找到插入位置，并直接修改沿途节点的子节点指针。但这样会丢失之前的状态。可持久化Trie的做法是：在需要修改的路径上，每个节点都新建一个副本，新节点的子节点指针中，继承那些没被修改的分支的旧指针，而将需要修改的分支指向新创建的下一个节点。

这样，原始路径被保留下来，新路径独立存在，但共享了大部分节点。

2. 版本管理：根节点数组

每个历史版本都有一个唯一的根节点。比如 root[0] 表示空字典树（版本0），root[1] 表示插入第1个数字后的树，root[2] 表示插入第2个数字后的树……以此类推。我们用一个数组或列表来存储这些根节点。

查询时，指定版本号（比如版本2），然后从 root[2] 开始，像普通Trie一样搜索即可。

3. 插入过程详解（以二进制01-Trie为例）

假设我们要向一个空Trie中插入数字 5（二进制 101，我们只用3位表示）。

  • 版本0：空树，root[0] 是一个空节点（没有子节点）。
  • 插入5（二进制101）：
    1. 从 root[0] 开始，创建新节点 newRoot1（版本1的根）。
    2. 看最高位（bit=2）：数字5的二进制第2位是 1，所以要在 root[0] 的 next[1] 分支（原来为空）创建一个新节点。
    3. 但 root[0] 的 next[0] 分支原本就是空，我们直接让 newRoot1 的 next[0] 指向 root[0] 的 next[0]（即空，但这样写是为了说明共享）。
    4. 然后递归到 newRoot1 的 next[1] 创建新节点 node2，处理下一位（bit=1，数字5的二进制第1位是 0），同样复制旧节点信息。
    5. 继续直到处理完所有位，最后在叶子节点标记计数+1。

最终，版本1只新创建了 新根 + 路径上的单独节点，未修改的部分（比如 root[0] 的其他分支）全部共享。

4. 查询过程

只要给定版本号，从对应根节点出发，完全按照普通Trie的查询逻辑进行。因为每个版本的结构是完整的，只是共享了节点。

5. 空间与时间

每次插入新增 O(L) 个节点（L为二进制位数，例如31位就是31个新节点）。总空间 O(N*L) 但实际远小于完全复制，因为大量节点共享。查询时间复杂度 O(L)。

新手容易犯的常见错误

❌ 错误1：直接修改旧节点，忘记复制

在递归插入时，容易写成直接修改 node->next[b]，而不是创建新节点。这样会破坏旧版本的数据。

正确做法：每次递归都要创建一个新节点，并复制旧节点的所有子节点指针。

❌ 错误2：更新cnt时忘记以子节点为准

有些实现里，每个节点记录以它为根的子树中的数字个数。当创建新节点后，需要从子节点重新计算 cnt，而不是简单地 +1。特别是当旧节点本身不是叶子时，需要累加两个子节点的cnt。

❌ 错误3：递归时没有处理好空指针

当旧节点为空（即该路径在旧版本中不存在）时，需要新建一个完整的路径，而不是试图复制旧节点。在代码中，需要判断 node 是否为 nullptr。

❌ 错误4：混淆版本号与插入次数

版本号通常从0开始（空树）。第一次插入后，版本号为1；第二次插入后，版本号为2。查询版本2意味着查询前两个插入后的状态。注意：版本号下标不一定等于插入次数，但通常我们让 roots[ver] 对应第ver次插入后的树（roots[0]为空）。

❌ 错误5：未处理重复插入

当同一个数字被插入多次，节点上的 cnt 应该累加。普通Trie中节点可能只标记存在与否，但可持久化Trie需要统计数量，否则查询“是否存在于某个版本”会出错。我们的代码中，在叶子节点用 cnt += 1，并向上维护总个数，这样就能正确处理重复插入。

完整可运行代码示例（C++ 和 Python）

原有代码已经非常标准，保留不变。下面我将补充更多注释和说明。

C++ 完整代码

#include <iostream>
#include <vector>
using namespace std;

const int MAX_BIT = 30;  // 数字二进制位数，0~30共31位（适合int范围）

// 可持久化Trie节点
struct PersistentTrieNode {
    PersistentTrieNode* next[2]; // 两个子节点指针：0和1
    int cnt;                     // 该节点为根的子树中包含的数字个数
    PersistentTrieNode() {
        next[0] = next[1] = nullptr;
        cnt = 0;
    }
};

class PersistentTrie {
private:
    vector<PersistentTrieNode*> roots; // 存储每个版本的根节点
    PersistentTrieNode* root0;         // 空版本根

    // 递归插入，返回新创建的节点
    PersistentTrieNode* insert(PersistentTrieNode* node, int num, int bit) {
        PersistentTrieNode* newNode = new PersistentTrieNode();
        if (node != nullptr) {
            // 复制旧节点的所有数据：子节点指针和cnt
            newNode->next[0] = node->next[0];
            newNode->next[1] = node->next[1];
            newNode->cnt = node->cnt;
        }
        if (bit < 0) {
            // 所有位处理完，表示到达叶子节点
            // 将数字计数加1（如果重复插入，cnt会累加）
            newNode->cnt++;
            return newNode;
        }
        int b = (num >> bit) & 1;  // 当前位的值（0或1）
        // 递归插入b分支：如果旧节点有该分支则传入，否则传入nullptr
        newNode->next[b] = insert(newNode->next[b] ? newNode->next[b] : nullptr, num, bit - 1);
        // 更新新节点的cnt：两个子节点cnt之和
        newNode->cnt = (newNode->next[0] ? newNode->next[0]->cnt : 0) + 
                       (newNode->next[1] ? newNode->next[1]->cnt : 0);
        return newNode;
    }

    // 查询版本ver中是否有数字num（实际查看节点上cnt）
    bool queryExist(PersistentTrieNode* node, int num, int bit) {
        if (node == nullptr) return false;
        if (bit < 0) {
            return node->cnt > 0;  // 如果cnt>0，说明至少有一个该数字
        }
        int b = (num >> bit) & 1;
        if (node->next[b] == nullptr) return false;
        return queryExist(node->next[b], num, bit - 1);
    }

    // 查询版本ver中与num异或的最大值
    int queryMaxXor(PersistentTrieNode* node, int num, int bit) {
        if (node == nullptr || bit < 0) return 0;
        int b = (num >> bit) & 1;
        int want = 1 - b;  // 我们希望走相反的分支，使异或值更大
        if (node->next[want] != nullptr) {
            // 如果能走相反分支，累加这一位的贡献并递归
            return (1 << bit) | queryMaxXor(node->next[want], num, bit - 1);
        } else {
            // 否则只能走相同分支，这一位贡献为0
            return 0 | queryMaxXor(node->next[b], num, bit - 1);
        }
    }

public:
    PersistentTrie() {
        root0 = new PersistentTrieNode(); // 空版本根
        roots.push_back(root0);           // 版本0：空树
    }

    // 在当前最新版本上插入数字，返回新版本索引（从1开始）
    int insert(int num) {
        PersistentTrieNode* lastRoot = roots.back();
        PersistentTrieNode* newRoot = insert(lastRoot, num, MAX_BIT);
        roots.push_back(newRoot);
        return roots.size() - 1; // 例如第一次插入后大小为2，索引1为版本1
    }

    // 查询版本ver（从0开始）中是否存在num
    bool exist(int ver, int num) {
        if (ver < 0 || ver >= (int)roots.size()) return false;
        return queryExist(roots[ver], num, MAX_BIT);
    }

    // 查询版本ver中与num异或的最大值（假设版本ver中有数字）
    int maxXor(int ver, int num) {
        if (ver < 0 || ver >= (int)roots.size()) return 0;
        return queryMaxXor(roots[ver], num, MAX_BIT);
    }

    int getVersionCount() { return roots.size(); }
};

int main() {
    PersistentTrie pt;
    // 每次插入后返回新版本号
    int v1 = pt.insert(5);   // 版本1
    int v2 = pt.insert(3);   // 版本2
    int v3 = pt.insert(7);   // 版本3

    cout << "版本2中是否存在3? " << (pt.exist(2, 3) ? "是" : "否") << endl;   // 是
    cout << "版本1中是否存在3? " << (pt.exist(1, 3) ? "是" : "否") << endl;   // 否（版本1只有5）
    cout << "版本3中与5异或的最大值: " << pt.maxXor(3, 5) << endl; // 5 xor 3 = 6, 5 xor 7 = 2, 最大6
    return 0;
}

Python 完整代码

class PersistentTrieNode:
    __slots__ = ('next', 'cnt')
    def __init__(self):
        self.next = [None, None]  # 两个子节点：0和1
        self.cnt = 0              # 该节点为根的子树中的数字个数

class PersistentTrie:
    MAX_BIT = 30  # 处理0~30共31位（int范围）

    def __init__(self):
        self.root_zero = PersistentTrieNode()  # 版本0根（空树）
        self.roots = [self.root_zero]          # 所有版本的根列表，索引即版本号

    def _insert(self, node: PersistentTrieNode, num: int, bit: int) -> PersistentTrieNode:
        """递归插入，返回新节点"""
        new_node = PersistentTrieNode()
        # 复制旧节点的数据
        if node is not None:
            new_node.next[0] = node.next[0]
            new_node.next[1] = node.next[1]
            new_node.cnt = node.cnt
        if bit < 0:
            # 到达叶子，计数+1（支持重复插入）
            new_node.cnt += 1
            return new_node
        b = (num >> bit) & 1  # 当前位的值
        # 递归插入b分支：如果旧节点有该分支则传入，否则传入None
        child = node.next[b] if node else None
        new_node.next[b] = self._insert(child, num, bit - 1)
        # 更新新节点的cnt
        cnt0 = new_node.next[0].cnt if new_node.next[0] else 0
        cnt1 = new_node.next[1].cnt if new_node.next[1] else 0
        new_node.cnt = cnt0 + cnt1
        return new_node

    def insert(self, num: int) -> int:
        """插入一个数字，返回新版本号（从1开始）"""
        last_root = self.roots[-1]
        new_root = self._insert(last_root, num, self.MAX_BIT)
        self.roots.append(new_root)
        return len(self.roots) - 1

    def _exist(self, node: PersistentTrieNode, num: int, bit: int) -> bool:
        if node is None:
            return False
        if bit < 0:
            return node.cnt > 0
        b = (num >> bit) & 1
        if node.next[b] is None:
            return False
        return self._exist(node.next[b], num, bit - 1)

    def exist(self, ver: int, num: int) -> bool:
        """查询版本ver中是否存在数字num"""
        if ver < 0 or ver >= len(self.roots):
            return False
        return self._exist(self.roots[ver], num, self.MAX_BIT)

    def _max_xor(self, node: PersistentTrieNode, num: int, bit: int) -> int:
        if node is None or bit < 0:
            return 0
        b = (num >> bit) & 1
        want = 1 - b  # 优先走相反分支
        if node.next[want] is not None:
            return (1 << bit) | self._max_xor(node.next[want], num, bit - 1)
        else:
            return self._max_xor(node.next[b], num, bit - 1)

    def max_xor(self, ver: int, num: int) -> int:
        """查询版本ver中所有数字与num异或的最大值"""
        if ver < 0 or ver >= len(self.roots):
            return 0
        return self._max_xor(self.roots[ver], num, self.MAX_BIT)

if __name__ == "__main__":
    pt = PersistentTrie()
    v1 = pt.insert(5)   # 版本1
    v2 = pt.insert(3)   # 版本2
    v3 = pt.insert(7)   # 版本3

    print("版本2中是否存在3?", pt.exist(2, 3))
    print("版本1中是否存在3?", pt.exist(1, 3))
    print("版本3中与5异或的最大值:", pt.max_xor(3, 5))  # 输出6

应用场景与延伸学习

可持久化Trie虽然代码稍显复杂，但它在解决“区间异或极值”和“可持久化线段树替代”等问题上有奇效。下面列举几个典型场景：

  1. 查询第i次插入前的字典树：直接使用 roots[i] 即可。
  2. 子数组异或最大值（LeetCode 1707 等）：先建立前缀异或的可持久化Trie，再对每个右端点查询区间内的最大异或值。
  3. 可持久化线段树的替代：当字符集很小（如二进制）时，可持久化Trie可以替代主席树，实现区间第k大（结合二分）或区间计数。
  4. 字符串版本管理：虽然字符集较大（26），但可持久化思想同样适用，只是节点复制成本稍高。

如果你想进一步了解可持久化数据结构，推荐学习 可持久化线段树（主席树）、可持久化并查集。它们共享同样的“复制节点、共享未改部分”的思想。

此外，掌握可持久化Trie后，你可以尝试自己实现一个支持历史版本中“插入”、“删除”、“查询前缀个数”的字典树（注意删除需要额外计数）。

可持久化Trie是通往高级数据结构的一扇门，虽然第一次接触可能觉得有些绕，但多写几次代码，你就能体会到这种“时间回溯”的奇妙之处了！

例题精讲

1单选题

可持久化Trie在插入一个新单词时，其空间复杂度与单词长度成正比的主要原因是什么？

A每次插入都会复制整个Trie树
B只复制从根到插入路径上的节点，其余节点共享
C每个节点都新增一个版本号
D使用数组存储所有节点，插入时重新分配整个数组
2单选题

在需要查询‘第i次插入操作之前，是否存在以某个前缀开头的字符串’这类问题时，可持久化Trie相比普通Trie的优势是什么？

A可以原地修改，节省空间
B能够保留所有历史版本，支持对任意时间点的前缀查询
C查询速度更快，达到O(1)
D不需要递归，实现更简单
3判断题

可持久化Trie插入一个新单词时，会为从根到该单词路径上的每一个节点创建一个新节点，这些新节点与旧版本中对应节点的子节点指针全部相同。

4填空题
以下是用C++实现可持久化Trie插入操作的代码片段（假设字符集为小写字母，使用数组存储节点）。请补全空白处的代码。

struct TrieNode {
    int ch[26];
    int cnt; // 经过该节点的单词数
} nodes[MAX_NODES];
int root[MAX_VERSIONS]; // 每个版本对应的根节点索引
int node_cnt = 0;

int insert(int pre_root, const string &s) {
    int cur_root = ++node_cnt;
    nodes[cur_root] = nodes[pre_root]; // 复制旧根节点
    int u = cur_root;
    for (char c : s) {
        int idx = c - 'a';
        int nxt = ___; // 填空1：创建新节点或复用？
        if (nxt == 0) {
            nxt = ___; // 填空2：创建一个新的子节点
        } else {
            // 需要复制该子节点以保持持久化
            int old = nxt;
            nxt = ++node_cnt;
            nodes[nxt] = nodes[old];
        }
        u = nodes[u].ch[idx] = nxt;
        nodes[u].cnt++;
    }
    return cur_root;
}
5填空题
以下是一个在可持久化Trie中查询某个版本中是否存在给定前缀的代码片段。假设节点结构如之前，root数组中存储每个版本的根节点索引。请补全空白处。

bool query(int version, const string &prefix) {
    int u = root[version];
    for (char c : prefix) {
        int idx = c - 'a';
        if (___ == 0) { // 填空1：判断子节点是否存在
            return false;
        }
        u = ___; // 填空2：移动到子节点
    }
    return true;
}