📖 第 9.3 章：Trie 树

🎯 学习目标

学完本章后，你将能够：

1. 理解 Trie 树（字典树）的结构与操作
2. 运用 Trie 树高效检索字符串集合
3. 掌握带计数的前缀统计与 01-Trie 求最大异或

9.3.0 问题引入

你有 N 个单词（总字符数 ≤ 10⁶），接下来有 Q 次查询，每次给出一个字符串，你需要回答：

1. 它是否在单词集合中？
2. 有多少个单词以它为前缀？

用 set<string> 每次查询是 O(|s| log N) 的字符串比较，前缀查询更是要扫描整个集合。Trie 树（字典树）把「字符串比较」变成「树上走路」，插入和查询都只要 O(|s|)——与集合大小无关。

集合：{"cat", "car", "can", "bat", "bar"}
查询："ca" → 有 3 个单词以它为前缀
查询："cab" → 不存在

9.3.1 Trie 树的结构

什么是 Trie？

Trie（发音：try）是一种树形数据结构，用来存储和查询字符串集合。

核心思想：用从根节点到某节点的路径来表示一个字符串。每条边对应一个字符，相同前缀的字符串共享路径。

可视化

存入字符串集合 {"cat", "car", "bat", "bar", "can"}：

        根节点
       /      \
      c         b
     / \       / \
    a   ?     a   ?
   /|\        |
  t r n       r  t（"bat"和"bar"共享"ba"前缀）
             / \
            ★   ★
         "bar" "bat"

※ ★ 表示在该节点结尾的字符串存在（"end" 标记）

同一前缀（如 "ca"）只存储一次，节省空间。

Trie 的数组实现

#include <bits/stdc++.h>
using namespace std;

// Trie 树（数组版，只支持小写字母）
const int MAXN = 500005;  // 最大节点数 = 总字符数

struct Trie {
    int ch[MAXN][26];  // ch[u][c] = 节点 u 的第 c 个子节点编号
    bool exist[MAXN];  // exist[u] = 以节点 u 结尾的字符串是否存在
    int cnt;           // 节点计数器（根节点为 0）
    
    Trie() : cnt(0) {
        memset(ch[0], 0, sizeof(ch[0]));  // 初始化根节点
        exist[0] = false;
    }
    
    // 插入字符串
    // 时间复杂度：O(|s|)
    void insert(const string& s) {
        int p = 0;  // 从根节点开始
        for (char c : s) {
            int ci = c - 'a';
            if (!ch[p][ci]) {
                ch[p][ci] = ++cnt;           // 新建节点
                memset(ch[cnt], 0, sizeof(ch[cnt]));
                exist[cnt] = false;
            }
            p = ch[p][ci];                    // 移动到下一个节点
        }
        exist[p] = true;  // 标记字符串末尾
    }
    
    // 查询字符串是否存在
    // 时间复杂度：O(|s|)
    bool find(const string& s) {
        int p = 0;  // 从根节点开始
        for (char c : s) {
            int ci = c - 'a';
            if (!ch[p][ci]) return false;  // 路径断了，不存在
            p = ch[p][ci];
        }
        return exist[p];  // 必须到达结尾标记的节点
    }
    
    // 查询是否有以 prefix 为前缀的字符串
    bool startsWith(const string& prefix) {
        int p = 0;
        for (char c : prefix) {
            int ci = c - 'a';
            if (!ch[p][ci]) return false;
            p = ch[p][ci];
        }
        return true;  // 路径存在即有此前缀（不需要 exist 标记）
    }
};

int main() {
    // 数组很大（约 52MB），必须放堆上——局部变量会爆栈
    static Trie trie;
    
    // 插入一些单词
    trie.insert("apple");
    trie.insert("app");
    trie.insert("apply");
    trie.insert("banana");
    
    // 查询
    cout << trie.find("apple")       << endl;  // 1（存在）
    cout << trie.find("app")         << endl;  // 1（存在）
    cout << trie.find("ap")          << endl;  // 0（路径存在，但没有标记）
    cout << trie.startsWith("ap")    << endl;  // 1（有以 "ap" 开头的字符串）
    cout << trie.startsWith("ban")   << endl;  // 1
    cout << trie.startsWith("cat")   << endl;  // 0
    
    return 0;
}

详细追踪：插入 "app" 和 "apple"

初始：只有根节点 0

插入 "app"：
  节点0 --'a'--> 节点1
  节点1 --'p'--> 节点2
  节点2 --'p'--> 节点3，exist[3] = true（"app" 结束）

插入 "apple"：
  节点0 --'a'--> 节点1（已存在，复用）
  节点1 --'p'--> 节点2（已存在，复用）
  节点2 --'p'--> 节点3（已存在，复用）
  节点3 --'l'--> 节点4（新建）
  节点4 --'e'--> 节点5，exist[5] = true（"apple" 结束）

现在 "app" 和 "apple" 共享前缀 "app"

9.3.2 Trie 树的经典应用

应用 1：单词频率统计（带计数的 Trie）

// 增加 count 数组记录每个节点被经过的次数
// count[u] = 以 u 为前缀的字符串的总插入次数

int count_prefix[MAXN];  // count[u] = 经过节点 u 的次数

void insert_with_count(const string& s) {
    int p = 0;
    for (char c : s) {
        int ci = c - 'a';
        if (!ch[p][ci]) {
            ch[p][ci] = ++cnt;
            count_prefix[cnt] = 0;
        }
        p = ch[p][ci];
        count_prefix[p]++;  // 每经过一个节点，计数 +1
    }
    exist[p] = true;
}

// 查询有多少个已插入字符串以 prefix 为前缀
int count_starts_with(const string& prefix) {
    int p = 0;
    for (char c : prefix) {
        int ci = c - 'a';
        if (!ch[p][ci]) return 0;
        p = ch[p][ci];
    }
    return count_prefix[p];
}

应用 2：01-Trie 求最大异或值

当数字以二进制形式插入 Trie 时，可以高效求「与某数异或值最大的数」。

原理：从最高位开始，贪心地走与当前位不同的那条路（使该位异或为 1）。

#include <bits/stdc++.h>
using namespace std;

// 01-Trie：维护整数集合，支持查询"与 x 异或最大的数"
// 按二进制位（从第30位到第0位）建树
const int BIT = 30;
const int MAXN_01 = 3000005;

int ch01[MAXN_01][2];  // 只有 0/1 两个子节点
int cnt01 = 0;

// 将整数 x 插入 01-Trie
void insert01(int x) {
    int p = 0;
    for (int i = BIT; i >= 0; i--) {
        int bit = (x >> i) & 1;       // 取第 i 位
        if (!ch01[p][bit]) ch01[p][bit] = ++cnt01;
        p = ch01[p][bit];
    }
}

// 查询与 x 异或值最大的数，返回最大异或值
int max_xor(int x) {
    int p = 0, res = 0;
    for (int i = BIT; i >= 0; i--) {
        int bit = (x >> i) & 1;
        int want = 1 - bit;            // 想要走与 bit 不同的方向（使异或为1）
        if (ch01[p][want]) {
            p = ch01[p][want];
            res |= (1 << i);           // 这一位异或为 1
        } else {
            p = ch01[p][bit];          // 没有理想方向，只能走 bit 方向
        }
    }
    return res;
}

// 示例：
// 集合 {3, 7, 9, 12}，查询与 6（二进制 110）异或最大
// 6 XOR 9 = 15（1111），是最大值
int main() {
    int arr[] = {3, 7, 9, 12};
    for (int x : arr) insert01(x);
    cout << max_xor(6) << endl;  // 输出 15
    return 0;
}

追踪 max_xor(6) 的过程（6 = 0...0110）：

第30~4位：全 0，Trie 中无这些位，跳过
第3位（bit=0）：want=1，ch[p][1] 存在（9=1001 的第3位=1）→ 走1，res |= 8
第2位（bit=1）：want=0，ch[p][0] 存在（9=1001 的第2位=0）→ 走0，res |= 4
第1位（bit=1）：want=0，ch[p][0] 存在（9=1001 的第1位=0）→ 走0，res |= 2
第0位（bit=0）：want=1，ch[p][1] 存在（9=1001 的第0位=1）→ 走1，res |= 1

最终 res = 8+4+2+1 = 15
对应的数是 9（9 XOR 6 = 15 ✓）

⚠️ 常见错误

💪 练习题（本章 5 道，全部含完整解答）

🟢 基础练习

题目 1：单词检索
给定 N 个单词，Q 次查询，每次询问某单词是否在词典中。要求插入和查询都用 Trie，总复杂度 O(总字符数)。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1000005;
int ch[MAXN][26];
bool exist[MAXN];
int tot = 0;

void insert(const string& s) {
    int p = 0;
    for (char c : s) {
        int ci = c - 'a';
        if (!ch[p][ci]) {
            ch[p][ci] = ++tot;
            fill(ch[tot], ch[tot] + 26, 0);
            exist[tot] = false;
        }
        p = ch[p][ci];
    }
    exist[p] = true;
}

bool query(const string& s) {
    int p = 0;
    for (char c : s) {
        int ci = c - 'a';
        if (!ch[p][ci]) return false;
        p = ch[p][ci];
    }
    return exist[p];
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int n, q;
    cin >> n;
    for (int i = 0; i < n; i++) {
        string w; cin >> w;
        insert(w);
    }
    cin >> q;
    while (q--) {
        string w; cin >> w;
        cout << (query(w) ? "YES" : "NO") << "\n";
    }
    return 0;
}

题目 2：最长公共前缀
给定 N 个字符串，求它们的最长公共前缀（LCP）。

示例：

输入：["flower","flow","flight"]
输出："fl"

方法 1（排序法）： 排序后只比较第一个和最后一个字符串的前缀，因为它们字典序差距最大，LCP 最短。

#include <bits/stdc++.h>
using namespace std;

string longestCommonPrefix(vector<string>& strs) {
    if (strs.empty()) return "";
    sort(strs.begin(), strs.end());
    string& first = strs.front();
    string& last  = strs.back();
    int i = 0;
    while (i < (int)first.size() && i < (int)last.size() && first[i] == last[i])
        i++;
    return first.substr(0, i);
}

int main() {
    vector<string> v = {"flower", "flow", "flight"};
    cout << longestCommonPrefix(v) << "\n";  // "fl"
    v = {"dog", "racecar", "car"};
    cout << longestCommonPrefix(v) << "\n";  // ""
    return 0;
}

方法 2（Trie法）： 将所有字符串插入 Trie，从根节点出发沿唯一路径走，直到遇到分叉或终止标记。

string lcp_trie(vector<string>& strs) {
    // 插入所有字符串后，从根出发找只有一个非空子节点且不是末尾的最长路径
    for (auto& s : strs) insert(s);
    
    string result = "";
    int p = 0;
    while (true) {
        if (exist[p]) break;  // 某字符串在此结束，不能继续
        int next = -1, cnt = 0;
        for (int i = 0; i < 26; i++) {
            if (ch[p][i]) { next = i; cnt++; }
        }
        if (cnt != 1) break;  // 有分叉，停止
        result += (char)('a' + next);
        p = ch[p][next];
    }
    return result;
}

🟡 进阶练习

题目 3：数组中任意两数的最大异或值
给定整数数组 nums，求任意两个元素异或的最大值。

示例：

nums = [3, 10, 5, 25, 2, 8]
最大异或：5 XOR 25 = 28
输出：28

思路： 将所有数插入 01-Trie，然后对每个数 x 查询「与 x 异或最大的数」并取全局最大值。

#include <bits/stdc++.h>
using namespace std;

const int BIT = 30;
const int MAXN = 3200005;
int ch[MAXN][2];
int tot = 0;

void insert(int x) {
    int p = 0;
    for (int i = BIT; i >= 0; i--) {
        int b = (x >> i) & 1;
        if (!ch[p][b]) ch[p][b] = ++tot;
        p = ch[p][b];
    }
}

int max_xor_with(int x) {
    int p = 0, res = 0;
    for (int i = BIT; i >= 0; i--) {
        int b = (x >> i) & 1;
        int want = 1 - b;  // 想走异位，使该位异或为 1
        if (ch[p][want]) {
            res |= (1 << i);
            p = ch[p][want];
        } else {
            p = ch[p][b];
        }
    }
    return res;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    
    int n; cin >> n;
    vector<int> nums(n);
    for (int& x : nums) { cin >> x; insert(x); }
    
    int ans = 0;
    for (int x : nums)
        ans = max(ans, max_xor_with(x));
    cout << ans << "\n";
    return 0;
}

追踪（nums = [3, 10, 5, 25, 2, 8]，查询 5 = 0b000101）： 下图展示对 5 的贪心查询——每一位尽量走相反位（绿色边），走不通时被迫走相同位（红色虚线边），最终沿 25 = 0b11001 的路径得到 res = 16 + 8 + 4 = 28 = 5 XOR 25。

题目 4：电话号码查找（前缀冲突检测）
给定 N 个电话号码，判断是否存在某号码是另一个号码的前缀。若存在输出 NO，否则输出 YES。

示例：

号码：["911","9116","91125"]
"911" 是 "9116" 的前缀 → 输出 NO

思路： 将所有号码插入 Trie，若插入过程中遇到已有终止标记的节点（当前号码是已插入号码的延伸），或插入完后该节点还有子节点（已插入号码是当前号码的前缀），则存在冲突。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1000005;
int ch[MAXN][10];  // 数字 0~9
bool is_end[MAXN];
int tot = 0;

// 插入号码，返回是否发现冲突
bool insert_check(const string& s) {
    int p = 0;
    for (char c : s) {
        int d = c - '0';
        if (is_end[p]) return true;   // 已有号码是当前号码的前缀
        if (!ch[p][d]) {
            ch[p][d] = ++tot;
            fill(ch[tot], ch[tot] + 10, 0);
            is_end[tot] = false;
        }
        p = ch[p][d];
    }
    // 插入完成，检查该节点是否已有子节点（当前号码是已有号码的前缀）
    for (int i = 0; i < 10; i++)
        if (ch[p][i]) return true;
    is_end[p] = true;
    return false;
}

int main() {
    int n; cin >> n;
    bool conflict = false;
    for (int i = 0; i < n; i++) {
        string s; cin >> s;
        if (insert_check(s)) conflict = true;
    }
    cout << (conflict ? "NO" : "YES") << "\n";
    return 0;
}

🔴 挑战练习

题目 5：最大数组异或路径（树上路径 + 01-Trie）
给定一棵有 N 个节点的树，每条边有权值。求树上任意一条路径，使路径上所有边权的异或和最大。

提示： 利用「两点路径的异或 = 两点到根的异或路径的异或」，先 DFS 求所有节点到根的异或距离，再用 01-Trie 求最大异或对。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
const int BIT = 30;
const int TRIE_MAXN = MAXN * 31 * 2;

// 01-Trie
int ch_trie[TRIE_MAXN][2];
int tot_trie = 0;

void insert_trie(int x) {
    int p = 0;
    for (int i = BIT; i >= 0; i--) {
        int b = (x >> i) & 1;
        if (!ch_trie[p][b]) ch_trie[p][b] = ++tot_trie;
        p = ch_trie[p][b];
    }
}

int max_xor_trie(int x) {
    int p = 0, res = 0;
    for (int i = BIT; i >= 0; i--) {
        int b = (x >> i) & 1;
        int want = 1 - b;
        if (ch_trie[p][want]) { res |= (1 << i); p = ch_trie[p][want]; }
        else p = ch_trie[p][b];
    }
    return res;
}

// 树 DFS
vector<pair<int,int>> adj[MAXN];
int dist[MAXN];  // dist[i] = 根到 i 的异或距离

void dfs(int u, int parent) {
    insert_trie(dist[u]);
    for (auto [v, w] : adj[u]) {
        if (v == parent) continue;
        dist[v] = dist[u] ^ w;
        dfs(v, u);
    }
}

int main() {
    int n; cin >> n;
    for (int i = 0; i < n - 1; i++) {
        int u, v, w; cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    
    dist[1] = 0;
    dfs(1, -1);  // 从节点 1 出发 DFS
    
    // 对每个节点，在 Trie 中找与其异或最大的节点
    int ans = 0;
    for (int i = 1; i <= n; i++)
        ans = max(ans, max_xor_trie(dist[i]));
    
    cout << ans << "\n";
    return 0;
}

关键原理：
设 d[u] = 根到 u 的边权异或和。
路径 u → v 的异或和 = d[u] XOR d[v]（因为公共前缀部分异或两次等于 0）。
所以只需在所有 d[i] 中找最大异或对，01-Trie 做到 O(N log W)。

📋 本章总结

• Trie 用「根到节点的路径」表示字符串，公共前缀只存一次
• 插入 / 查询都是 O(|s|)，与集合大小无关
• exist 标记区分「恰好是这个串」与「是某个串的前缀」
• 01-Trie 把整数按二进制位建树，贪心走「相反位」求最大异或

💡 章节联系： Trie 是第 9.5 章 AC 自动机的骨架——在 Trie 上加一圈 fail 指针，它就能在文本上「自动机式」地多模式匹配。前缀冲突、前缀计数这类问题也常与第 3.7 章的哈希技术结合（哈希判等 + Trie 组织）。