Trie 字典树 & 二叉堆

iChen · 2026-01-09 16:58:46 · 算法·理论

说在前面

校内 OJ 将 Trie 和二叉堆放在了一个小节中，故本文章将两个总结缝合。除应用外的部分主要面向校内外的初学者。

本文 Trie 部分由 @xuezhiyu 编写，二叉堆部分由 @iChen 编写。

从超模 xzy 和菜狗 iC 编写的文章质量差异中能看出两人间悬殊的实力差异。膜拜 xzy！

Trie

引入

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

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

例如节点 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 练习题单

二叉堆

结构

二叉堆是一棵完全二叉树，满足堆性质：任意一对父子结点中父结点的权值不小于其子结点。

可以从此性质发现树上任意一根链从根结点拉到叶子结点经过的权值是单调不增的。不难发现根结点的权值是全树中最大的，所以我们叫它大根堆。反之，如果使任意父结点的权值不大于其子结点，根结点的权值就是全树中最小的，这就是小根堆。

我们可以在向二叉堆（集合）中不断插入和删除元素的同时维护其堆性质，就可以随时直接访问根结点 \mathcal O(n) 地得到当前集合的最大或最小值。这也就是二叉堆的应用场景。

以下内容根据笔者习惯使用小根堆进行讲解。

维护

主要是如何在插入和删除元素时维护其性质。

插入

前面说过，二叉堆是完全二叉树，所以我们直接把新插入的元素甩到按照父子结点二倍表示法的下一个位置，也就是最后一层最后一个位置去：

如图，我们在二叉堆中插入一个元素 2。

但是这时二叉堆不符合堆性质了，怎么办？

我们发现不符合性质的一对父子是 7 和 2，7 > 2 而 7 在 2 的上方，于是选择交换 2 和 7 的结点的权值，如图：

现在出现了新的一对不符合堆性质的父子结点 2 和 3，同样进行交换权值操作：

而 2 现在与它的新父节点满足堆性质，整个二叉堆都满足堆性质了。

以上操作即为向上调整操作。

回顾向上调整操作为什么是正确的？

设插入的权值为 a，一对父子结点间关系不满足堆性质称为在这对父子间发生了矛盾。

那么每次调整后整个二叉堆中只可能出现 a 与其新的父结点矛盾或不出现矛盾，所以我们可以继续和父结点交换权值。

如图，为什么说发现矛盾（b > a）并交换权值后，a 只可能与新的父结点 d 发生矛盾而不会和 c 发生矛盾？

由于原二叉堆满足堆性质，有 b < c，而我们在 b > a 时调整权值，由于小于号的传递性，a < c，故不可能出现 a 与 c 的矛盾。

那么理解向上调整后，尝试写出实现插入操作的代码。

int data[N], siz; // 分别存储结点权值，当前二叉堆大小 
inline void swim (int pos) { // 向上调整 
    while (pos != 1 and data[pos >> 1] > data[pos]) {
        // 到达根结点或者未出现矛盾作为出口
        swap(data[pos], data[pos >> 1]); // 交换权值 
        pos >>= 1; // 向上递推，来到新结点 
    }
}
inline void insert (int val) {
    data[++ siz] = val; // 在最后插入一个新结点，保证完全二叉树结构 
    swim(siz); // 向上调整此新结点的权值 
}

删除

实现删除堆顶的操作。

隔壁 BST（二叉搜索树）的做法是，找到两个子结点 a, b 中权值更小的 a 顶替堆顶，然后从 a 向 b 连边，删除堆顶的同时依然满足堆性质。但二叉堆不一样，它需要保持完全二叉树的形态。

那么删除完全二叉树的哪个结点能使它保持完全二叉树的形态？最后一层最后一个结点，也就是按父子二倍表示法编号最大的结点。

那么直接将最后一层最后一个结点也就是 siz 号结点与根互换权值，然后将这个结点删去。

接下来问题出在根结点了，考虑向下调整以维护堆性质。

设从叶子结点搬到根结点的权值为 a，那么此时只可能在 a 与其儿子间发生矛盾，我们分类讨论：

设 a 的两个儿子结点权值分别为 b, c，使 b\leqslant c：

如何理解？如果我们要进行调整，那么需要使一个儿子结点与 a 互换权值。如果与 c 交换，那么 c 成为了 b 的父亲结点，而 b\leqslant c，在 b < c 时会出现矛盾。而我们使 a 与 b 交换就能避免这种情况。

总结做法，找到两个儿子结点权值中的更小值，判断是否需要调整。若需要则和儿子结点中权值更小的一个交换权值，向下递推。

那么可以打出以下代码：

inline void sink (int pos) { // 向下调整操作 
    while (pos << 1 <= siz) { // 假如不是叶子结点 
        int nxt = pos << 1; // 暂且将权值更小的儿子结点设为 
        if (nxt < siz and data[nxt + 1] < data[nxt]) nxt ++;
        // 有右儿子 & 右儿子权值小于左儿子：权值更小的结点设为右儿子 
        if (data[pos] > data[nxt]) { // 发生矛盾，需要调整 
            swap(data[pos], data[nxt]); // 交换权值 
            pos = nxt; // 向下递推 
        } else break; // 无矛盾，停止调整 
    }
}
inline void pop () {
    swap(data[1], data[siz]); // 把根结点与最后一个结点交换权值 
    siz --; // 删除最后一个结点 
    sink(1); // 从根结点开始向下调整 
}

到这里就已经完成了所有二叉堆的基本功能的实现啦，封装一下得到：

struct Heap {
    int siz, data[N];
    inline void swim (int pos) {
        while (data[pos] < data[pos >> 1]) {
            swap(data[pos], data[pos >> 1]);
            pos >>= 1;
        }
    }
    inline void sink (int pos) {
        while (pos << 1 <= siz) {
            int nxt = pos << 1;
            if (nxt < siz and data[nxt + 1] < data[nxt]) nxt ++;
            if (data[pos] > data[nxt]) {
                swap(data[pos], data[nxt]);
                pos = nxt;
            } else break;
        }
    }
    inline void insert (int val) {
        data[++ siz] = val;
        swim(siz);
    }
    inline void pop () {
        swap(data[1], data[siz]);
        siz --;
        sink(1);
    }
    inline int top () {
        return data[1];
    }
    inline bool empty () {
        return !siz;
    }
    inline int size () {
        return siz;
    }
} heap;

建堆

给出一个乱序的序列，把所有元素插入一个空二叉堆中，如何实现？

顺序插入

考虑每次将新插入的结点放入二叉堆中最后一层的最后一个结点之后，即和我们的插入操作一样，那么单次插入操作是 \mathcal O(\log n) 的，总时间复杂度使 \mathcal O(n\log n) 的。

排序

将整个序列排序后，直接按照父子二倍表示法的序号插入堆中，排序时间复杂度 \mathcal O(n\log n)。

向上调整

先将整个乱序序列直接无脑放入堆中，显然此时整个堆中有很多矛盾。然后开始从根结点向下按照 BFS 序轮流向上调整，也就是从根结点开始向下逐步理顺每层的结点使其满足堆性质。注意，设一个结点的所在层数是 k，编号为 i，那么它向上调整的复杂度是 \mathcal O(k) 或者 \mathcal O(\log i) 而并非全局下悲观的 \mathcal O(\log n)。

总复杂度：\displaystyle\sum _{i=1} ^{n} \log i = \mathcal O(n\log n)。

向下调整

首先和向上调整一样把整个乱序序列无脑放入堆中。然后从编号大到小依次进行向下调整。也就可以理解为从下向上对每个结点的以两个儿子结点的已经满足堆性质的两棵子树作合并操作。

以上长难句有点难理解，还是看这张图：

（ps：b, c 不一定是叶子结点）

由于我们从下层向上层调整，我们调整到 a 时，其两个儿子 b, c 往下的子树已经满足堆性质了。那么这个时候对于以 a 为根的子树，矛盾只可能出在 a, b, c 中，于是可以通过对 a 的向下调整使以 a 为根的子树满足堆性质。这样层层递归，每次合并两个子树，一直到根结点就可以完成建堆了。

同样设一个结点的所在层数是 k，编号为 i，那么它向下调整的复杂度是 \mathcal O(\log n - k) 或者 \mathcal O(\log n - \log i)。

时间复杂度证明搬一下 OI-Wiki 的，wtcl 不会证。

对于向上/向下调整复杂度差异的感性理解

（纯感性理解，严谨度为 0\%）

在向上调整和向下调整两个方法中，都对二叉堆里每一个结点进行了一次向上/向下调整，为什么时间复杂度存在一个 \log 的差异？

在完全二叉树中，显然发现处于下层结点数量远多于上层结点数量。

回顾向上调整，最差情况下会一直向上跳直到最上面一层也就是根结点；而在向下调整中最差情况下会一直向下跳直到最下面一层也就是叶子结点。

对于在下层的结点，其与叶子结点的距离比与根结点的距离近，也就是对于下层结点来说使它们向下调整时间复杂度更优；对于在上层的结点，其与根结点的距离比与叶子结点的距离近。也就是对于上层结点来说使它们向上调整时间复杂度更优。

但是下层结点的数量更多，如果使用向上调整，虽然使数量处于少数的上层结点可以很快完成调整，但数量处于多数的下层结点需要跑更远去到达根结点；如果使用向下调整，使数量处于多数的下层结点快速完成调整，使处于少数的上层结点跑更远些到达叶子节点，肯定是更优的。

说了半天的意思就是：

转换为公式也就是：

也就是我们前面分别算过的复杂度了。

由此可以感性理解为什么向下调整优于向上调整。

STL 平替

有一个奇妙的 STL 容器叫做 priority queue（优先队列），实现了二叉堆的所有操作。而相比于其它 STL，priority queue 的常数并不显得特别大，基本可以完全代替二叉堆。如果一些题极端卡常才可能会考虑选择使用手写的二叉堆。

首先需要头文件：

#include <queue>

优先队列在定义时默认大根堆，也可以自行选择使用小根堆或大根堆：

priority_queue <int> q; // 默认为大根堆
priority_queue <int, vector <int>, less <int>> q; // 大根堆
priority_queue <int, vector <int>, greater <int>> q; // 小根堆

以下是成员函数：

q.push(x); // 将 x 元素插入堆中
q.top(); // 返回堆顶元素
q.pop(); // 删除堆顶元素
q.empty(); // 返回堆是否为空
q.size(); // 返回堆的大小

另外，如果堆中元素类型定为结构体，需要自行重载运算符。

其实我也不是很理解为什么优先队列的常数较其它 STL 来说更小，于是和 deepseek 进行了辩论，得到的理由如下：

• 默认基于 std::vector 实现，存储连续内存，缓存友好。
• 逻辑结构是完全二叉树，通过下标索引计算父子位置，无需指针开销。

并且在千万级的数据下，其性能与手写堆相比差异不超过 20\%，相当优异。

哦对，如果想要清空队列，STL 的优先队列没有 clear 函数，你需要一个一个删除堆顶。而手写堆直接 siz = 0 即可。这也是在理论时间复杂度上手写堆唯一的优势了（吗？）

拓展应用

双端优先队列

做 [CSP-S 2020] 贪吃蛇 时觉得这个实现挺巧妙的，于是自己给这玩意起了个七糟八乱的名字。其作用是可以在优先队列的队头队尾进行查询插入删除操作，使用四个堆实现，常数惊人谨慎使用。

为什么我叫它双端优先队列？我认为这东西就是对双端队列和优先队列的缝合，向里面插入元素可以保证这个序列有序，而又可以对这个序列的头和尾也就是最大和最小值进行操作。

我们首先需要一个大根堆 q1 一个小根堆 q2，主要的操作在这里面进行。当我们需要插入某元素，直接往两个堆中都插入此元素。查询堆中最大最小值都直接查询 q1 或 q2 的堆顶即可。

但是如果想要进行删除操作呢？我们想将堆中最大值删除，对于 q1 直接删除堆顶即可，而对于 q2 呢？那我们可以再开一个大根堆 dq1 和小根堆 dq2，分别用来临时保存 q1 和 q2 中本应删除但仍未删除的元素。

比如删除最大值 x，对于 q2，我们在 dq2 中插入 x。当要查询 q2 堆顶时，看看当前堆顶是否也是 dq2 堆顶。如果是，证明之前已经删除过此元素，临时记录在 dq2 中了，那么将 q2 和 dq2 堆顶都删除，接着查询下一个 q2 堆顶是否是 dq2 堆顶也就是曾被删除，直到找到没被删除的堆顶，得到答案。q1 和 dq1 同理。

尝试代码实现：

（查询时保证堆不为空）

struct priority_deque {
    priority_queue <int, vector <int>, less<int>> q1, dq1;
    priority_queue <int, vector <int>, greater <int>> q2, dq2;
    inline void insert (int data) {
        q1.push(data), q2.push(data);
    }
    inline int top_max () {
        while (q1.top() == dq1.top()) q1.pop(), dq1.pop();
        return q1.top();
    }
    inline int top_min () {
        while (q2.top() == dq2.top()) q2.pop(), dq2.pop();
        return q2.top();
    }
    inline void delete_max () {
        while (q1.top() == dq1.top()) q1.pop(), dq1.pop();
        dq2.push(q1.top());
        q1.pop();
    }
    inline void delete_min () {
        while (q2.top() == dq2.top()) q2.pop(), dq2.pop();
        dq1.push(q2.top());
        q2.pop();
    }
    inline bool empty () {
        return q1.size() == dq1.size();
    }
    inline int size () {
        return q1.size() - dq1.size();
    }
};

对顶堆

个人感觉运用场景很限制。大概率是因为 wtcl 刷题量不够目前还没在做题中用过这个东西吧。

解决这个模型：

• 维护一个序列，可动态插入元素和查询序列中较小的中位数。

中位数就是把序列切两半，然后中间那个数嘛。所以我们同样地把序列分为两个堆维护，一个大根堆装较小的那一半数，一个小根堆装较大的那一半数，长这个样子：

如图，红色的两个位置就是两个堆的堆顶，我们可以随时对这两个元素查询和删除。

我们需要保证把这个序列刚好切成两半，那么就要使左边的大根堆和右边的小根堆的元素数量相等或者大根堆比小根堆多 1。那么大根堆的堆顶就是我们维护的较小的中位数。

如何进行插入操作？只需要将插入的元素与大根堆堆顶比大小，决定它该在序列左半段还是右半段然后甩进相应的堆中即可。

那插入完成后左右大小不平衡了怎么办？把元素数量多了的那个堆的堆顶弹出来插入另一个堆即可。

呃呃目前大概就是这些了。

Q：为啥不讲例题？
A：有堆标签的题目的考察点中对于堆的含量基本小于 20\%。

完成 练习题 以巩固对二叉堆的理解！

建议手写二叉堆，如果用 STL 无法起到巩固知识点的作用，但是我也卡不了 STL 还是纯凭自觉吧