字典树（trie）详解

xuezhiyu · 2026-01-07 17:33:45 · 算法·理论

引入

字典树是一种存储字符串的树形数据结构。具体来说，每条边有一个字符，每个节点到儿子的边的字符不重。同时每个节点都代表一个字符串，为从根节点出发向下走到这个节点路上经过所有边的字符组成的字符串。

下面给出了字典树的一个例子：

例如节点 10 表示的字符串为 \mathtt{acc}，节点 7 代表的字符串为 \mathtt{ca}。

当我们把一个可重字符串集维护成字典树时，我们需要知道那些字符串有几个，因此会在每个节点 u 处打上标记 c_u，表示节点 u 代表的字符串 S_u 在当前可重集中有 c_u 个。

例如如果把以下字符串集 \{\mathtt{aba},\mathtt{aca},\mathtt{acc},\mathtt{acc},\mathtt{b},\mathtt{ca},\mathtt{caa}\} 存到上面的字典树中，那么 c_8=c_9=c_3=c_7=c_{11}=1,c_{10}=2，其余均为 0。

因为每个节点到儿子的边的字符不重，所以任何在字典树上的字符串都有唯一的一个节点来代表它。

字典树具有的最重要的性质是任意两个字符串集中不等的字符串 S_1,S_2，S_1 为 S_2 前缀 当且仅当 代表 S_1 的节点为 S_2 节点的祖先，正确性显然。这条性质说明字典树就是维护前缀类信息的数据结构，这也是它大部分应用所基于的性质。

代码实现细节

一般会用 \delta_{u,i} 表示节点 u 边上字符为 i 的儿子，反映到代码上就是一个数组 ch[u][i] 表示 \delta_{u,i}，如果没有记为 0 或 -1，取决于你的代码习惯。

为了节省空间，ch 一般开到 ch[N][M]，其中 N 是可能用到的 trie 节点个数，上界为字符串长度之和，M 是字符集大小，即 |\Sigma|。通过一个函数（我一般用 get）来把字符转换为唯一对应的数，用于访问 ch 的第二维。

根节点取 0 或者 1，同时 trie 肯定是动态开点的，记一个 idx 即可，以下设根节点为 1。

插入字符串

按照定义从根节点出发往下找即可，发现没有创建的节点就创建。

int ch[N][M], cnt[N], idx = 1, rt = 1;
int get(char);

void insert(const string& s) {
    int u = rt;
    for (char i : s)
        u = ch[u][get(i)] ? ch[u][get(i)] : ch[u][get(i)] = ++idx;
    cnt[u]++;
}

删除字符串

从上往下找到然后让 c_u 减去 1 即可。

void remove(const string& s) {
    int u = rt;
    for (char i : s) u = ch[u][get(i)];
    if (u) cnt[u]--;
}

应用

多次查询前缀/后缀个数

即给定 n 个模式串 s_1,s_2,\cdots,s_n，每次询问给定一个字符串 t 求有多少个模式串是它的前缀/后缀。

根据 trie 的性质，插入所有模式串后，如果找前缀个数，从根结点出发按 t 走若没有点就停下，路上经过的点的 c 之和即为答案；找后缀就找到代表 t 的节点，查询子树 c 之和即可。

:::success[P8306 【模板】字典树（找前缀个数）代码]

题目链接

#include <iostream>
#define endl '\n'

using namespace std;

constexpr int N = 1e5 + 10, M = 1e6 + 10, K = 26;
int n, m;
int idx = 1, ch[M][K], cnt[M];

int get(char ch) { return ch - 'a'; }

void push(const string& s) {
    int u = 1;
    for (char i : s) {
        if (!ch[u][get(i)]) ch[u][get(i)] = ++idx;
        u = ch[u][get(i)];
    }
    cnt[u]++;
}

int query(const string& s) {
    int u = 1, res = 0;
    for (char i : s)
        res += cnt[u = ch[u][get(i)]];
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        static string temp;
        cin >> temp;
        push(temp);
    }
    for (int i = 1; i <= m; i++) {
        static string temp;
        cin >> temp;
        cout << query(temp) << endl;
    }
    return 0;
}

:::

求序列两两异或和最大值

:::info[P10471 最大异或对 The XOR Largest Pair]{open}

给定 N 个整数 A_1,A_2,\cdots,A_N，求两两异或和的最大值。

:::

我们把每个整数的二进制高位补零到 31 位后从高位到低位插入 trie 中，称为 01-trie。

首先如果查询一个整数和 trie 中所有数异或和的最大值，根据位运算的性质，贪心地让高位更优一定是全局最优的，因此我们可以从高位往低位枚举，如果 trie 中存在和该整数异或后该位为 1，表现为当前遍历节点存在该数在该位值异或 1 的子节点，那么就必定要走这个儿子，否则一定不是最优的。否则只能走另一个儿子。因为 trie 中每个数插入的长度固定，除了最后一层节点每个节点都有至少一个儿子。

于是就可以一个一个把整数插入 Trie 中，在插入整数前查询一下当前 Trie 中和该整数异或和最大值即可。

:::success[上述问题代码]

#include <iostream>

using namespace std;

constexpr int N = 1e5 + 10, M = 32e5 + 10, K = 31;
int n, ans = 0;
int idx = 1, ch[M][2];

void push(int val) {
    int u = 1;
    for (int i = K - 1; ~i; i--) {
        if (!ch[u][val >> i & 1]) ch[u][val >> i & 1] = ++idx;
        u = ch[u][val >> i & 1];
    }
}

int query(int val) {
    int u = 1, res = 0;
    for (int i = K - 1; ~i; i--) {
        int j = val >> i & 1;
        if (ch[u][j ^ 1]) { // 能走一定走，累计答案
            u = ch[u][j ^ 1], res |= 1 << i;
        } else {
            u = ch[u][j];
        }
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int val; cin >> val;
        if (i > 1) ans = max(ans, query(val));
        push(val);
    }
    cout << ans << endl;
    return 0;
}

:::

Trie 优化建图

根据 Trie 的性质，和字符串前后缀有关的问题可以利用 Trie 的树形结构，来优化图论模型。下面给出了一道例题。

:::info[P6965 [NEERC 2016] Binary Code]{open}

给定 n 个 01 串，每个 01 串至多有一位未知，可填 0 或 1，求是否存在一组方案，使得任意一个字符串都不是其它任意字符串的前缀。

:::

每个节点都先建立一棵 01 trie 保存它自己的权值，随后在一次深度优先搜索时每个节点把它子节点的 trie 合并起来加上 1 再合并上它自己权值的 trie 就得到了它子树所有元素的异或 01 trie，查询全局异或和就得到了当前节点的价值。

这样就得到了一种 \mathcal O(n\log V) 的算法，足以通过本题。

:::success[题目代码]

#include <cstdint>
#include <iostream>
#include <vector>
#define int int64_t // 十年 OI 一场空，________

using namespace std;

constexpr int N = 525020, K = 25, M = N * K;
int n, a[N], h[N], e[N], ne[N], idx, ans;
// 实际上不用垃圾回收也可以，空间复杂度仍为 nlogV
int m, ch[M][2], siz[M], val[M], pool[M], pooltop;

void addedge(int u, int v) {
    ++idx, e[idx] = v, ne[idx] = h[u], h[u] = idx;
}

void clear(int u) { ch[u][0] = ch[u][1] = siz[u] = val[u] = 0; }
void pushnode(int u) { clear(pool[pooltop++] = u); }
int getnode() { return pooltop ? pool[--pooltop] : ++m; }

void pushup(int u) { // 01 trie 的 pushup
    if (!ch[u][0] && !ch[u][1]) return;
    siz[u] = siz[ch[u][0]] + siz[ch[u][1]];
    val[u] = ((val[ch[u][0]] ^ val[ch[u][1]]) << 1) | (siz[ch[u][1]] & 1);
}

int build(int x) { // 按一个权值建树
    int rt = getnode(), u = rt;
    siz[rt] = 1, val[u] = x;
    for (int i = 0; i < K; i++)
        u = ch[u][x >> i & 1] = getnode(), siz[u] = 1, val[u] = x >> (i + 1);
        // 注意这里 val 要取 x >> (i+1) 因为异或和是局部的 
    return rt;
}

int merge(int u, int v) { // 01 trie 合并
    if (!u || !v) return u | v;
    if (!ch[u][0] && !ch[u][1]) siz[u] += siz[v];
    ch[u][0] = merge(ch[u][0], ch[v][0]);
    ch[u][1] = merge(ch[u][1], ch[v][1]);
    return pushup(u), pushnode(v), u;
}

void addall(int u) { // 全局加 1
    if (!u) return;
    swap(ch[u][0], ch[u][1]);
    addall(ch[u][0]), pushup(u);
}

int dfs(int u) {
    int rt = 0;
    for (int i = h[u]; i; i = ne[i])
        rt = merge(rt, dfs(e[i])); // 合并儿子的 trie
    addall(rt); // 这里加 1 有助于减小常数
    rt = merge(rt, build(a[u]));
    return ans += val[rt], rt; // 查询全局异或和，就是根节点的 val
}

signed main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 2, f; i <= n; i++)
        cin >> f, addedge(f, i);
    dfs(1);
    cout << ans << endl;
    return 0;
}

:::

练习题

Trie 练习题单