字典树 (Trie)

定义

字典树，英文名 trie。顾名思义，就是一个像字典一样的树。

引入

先放一张图：

可以发现，这棵字典树用边来代表字母，而从根结点到树上某一结点的路径就代表了一个字符串。举个例子， 表示的就是字符串 caa。

trie 的结构非常好懂，我们用 表示结点 的 字符指向的下一个结点，或着说是结点 代表的字符串后面添加一个字符 形成的字符串的结点。（ 的取值范围和字符集大小有关，不一定是 。）

有时需要标记插入进 trie 的是哪些字符串，每次插入完成时在这个字符串所代表的节点处打上标记即可。

实现

放一个结构体封装的模板：

=== "C++"

```cpp
struct trie {
  int nex[100000][26], cnt;
  bool exist[100000];  // 该结点结尾的字符串是否存在

  void insert(char *s, int l) {  // 插入字符串
    int p = 0;
    for (int i = 0; i < l; i++) {
      int c = s[i] - 'a';
      if (!nex[p][c]) nex[p][c] = ++cnt;  // 如果没有，就添加结点
      p = nex[p][c];
    }
    exist[p] = 1;
  }

  bool find(char *s, int l) {  // 查找字符串
    int p = 0;
    for (int i = 0; i < l; i++) {
      int c = s[i] - 'a';
      if (!nex[p][c]) return 0;
      p = nex[p][c];
    }
    return exist[p];
  }
};
```

=== "Python"

```python
class trie:
    nex = [[0 for i in range(26)] for j in range(100000)]
    cnt = 0
    exist = [False] * 100000  # 该结点结尾的字符串是否存在

    def insert(self, s):  # 插入字符串
        p = 0
        for i in s:
            c = ord(i) - ord('a')
            if not self.nex[p][c]:
                self.cnt += 1
                self.nex[p][c] = self.cnt  # 如果没有，就添加结点
            p = self.nex[p][c]
        self.exist[p] = True

    def find(self, s):  # 查找字符串
        p = 0
        for i in s:
            c = ord(i) - ord('a')
            if not self.nex[p][c]:
                return False
            p = self.nex[p][c]
        return self.exist[p]
```

应用

检索字符串

字典树最基础的应用——查找一个字符串是否在“字典”中出现过。

AC 自动机

trie 是

维护异或极值

将数的二进制表示看做一个字符串，就可以建出字符集为 的 trie 树。

维护异或和

01-trie 是指字符集为 的 trie。01-trie 可以用来维护一些数字的异或和，支持修改（删除 + 重新插入），和全局加一（即：让其所维护所有数值递增 1，本质上是一种特殊的修改操作）。

如果要维护异或和，需要按值从低位到高位建立 trie。

一个约定：文中说当前节点 往上 指当前节点到根这条路径，当前节点 往下 指当前结点的子树。

插入 & 删除

如果要维护异或和，我们 只需要 知道某一位上 0 和 1 个数的 奇偶性 即可，也就是对于数字 1 来说，当且仅当这一位上数字 1 的个数为奇数时，这一位上的数字才是 1，请时刻记住这段文字：如果只是维护异或和，我们只需要知道某一位上 1 的数量即可，而不需要知道 trie 到底维护了哪些数字。

对于每一个节点，我们需要记录以下三个量：

• ch[o][0/1] 指节点 o 的两个儿子，ch[o][0] 指下一位是 0，同理 ch[o][1] 指下一位是 1。
• w[o] 指节点 o 到其父亲节点这条边上数值的数量（权值）。每插入一个数字 x，x 二进制拆分后在 trie 上 路径的权值都会 +1。
• xorv[o] 指以 o 为根的子树维护的异或和。

具体维护结点的代码如下所示。

插入和删除的代码非常相似。

需要注意的地方就是：

• 这里的 MAXH 指 trie 的深度，也就是强制让每一个叶子节点到根的距离为 MAXH。对于一些比较小的值，可能有时候不需要建立这么深（例如：如果插入数字 4，分解成二进制后为 100，从根开始插入 001 这三位即可），但是我们强制插入 MAXH 位。这样做的目的是为了便于全局 +1 时处理进位。例如：如果原数字是 3（11），递增之后变成 4（100），如果当初插入 3 时只插入了 2 位，那这里的进位就没了。

• 插入和删除，只需要修改叶子节点的 w[] 即可，在回溯的过程中一路维护即可。

全局加一

所谓全局加一就是指，让这棵 trie 中所有的数值 +1。

形式化的讲，设 trie 中维护的数值有 , 全局加一后 其中维护的值应该变成

过程

我们思考一下二进制意义下 +1 是如何操作的。

我们只需要从低位到高位开始找第一个出现的 0，把它变成 1，然后这个位置后面的 1 都变成 0 即可。

下面给出几个例子感受一下：（括号内的数字表示其对应的十进制数字）

1000(8)  + 1 = 1001(9)  ;
10011(19) + 1 = 10100(20) ;
11111(31) + 1 = 100000(32);
10101(21) + 1 = 10110(22) ;
100000000111111(16447) + 1 = 100000001000000(16448);

对应 trie 的操作，其实就是交换其左右儿子，顺着 交换后 的 0 边往下递归操作即可。

回顾一下 w[o] 的定义：w[o] 指节点 o 到其父亲节点这条边上数值的数量（权值）。

有没有感觉这个定义有点怪呢？如果在父亲结点存储到两个儿子的这条边的边权也许会更接近于习惯。但是在这里，在交换左右儿子的时候，在儿子结点存储到父亲这条边的距离，显然更加方便。

01-trie 合并

指的是将上述的两个 01-trie 进行合并，同时合并维护的信息。

可能关于合并 trie 的文章比较少，其实合并 trie 和合并线段树的思路非常相似，可以搜索“合并线段树”来学习如何合并 trie。

其实合并 trie 非常简单，就是考虑一下我们有一个 int merge(int a, int b) 函数，这个函数传入两个 trie 树位于同一相对位置的结点编号，然后合并完成后返回合并完成的结点编号。

过程

考虑怎么实现？

分三种情况：

• 如果 a 没有这个位置上的结点，新合并的结点就是 b

• 如果 b 没有这个位置上的结点，新合并的结点就是 a

• 如果 a,b 都存在，那就把 b 的信息合并到 a 上，新合并的结点就是 a，然后递归操作处理 a 的左右儿子。

  提示：如果需要的合并是将 a，b 合并到一棵新树上，这里可以新建结点，然后合并到这个新结点上，这里的代码实现仅仅是将 b 的信息合并到 a 上。

实现

其实 trie 都可以合并，换句话说，trie 合并不仅仅限于 01-trie。

可持久化字典树

参见