Trie 树CSP-S

💡 核心思想

Trie（前缀树/字典树）是一种树形数据结构，每条边代表一个字符，从根到某节点的路径上的字符组成一个字符串。支持 $O(|s|)$ 的插入、查询和前缀匹配。变体包括 01-Trie（处理异或问题）。

🎯 直觉理解

字典树（Trie）是"按前缀存储字符串"的树：根到每个节点的路径就是一个前缀，每个节点有 26 个子节点指针（或数组）。插入一个单词就是在树上走一遍，没有的路就开。

用途：统计每个单词出现次数（在结尾节点计数）、查某个前缀有多少个单词、最大异或对（数字按二进制插入）。

实现用数组模拟：trie 二维数组存节点转移，cnt 数组计数。空间注意：总节点数 = 所有字符串长度之和，别开小了。理解"公共前缀共享节点"就理解了 Trie 的空间优势。

📝 算法流程

1. 插入：沿字符路径走，不存在则创建新节点
2. 查询：沿路径走，走不到则不存在
3. 每个节点维护 son[26] 和 end 标记
4. 01-Trie：son[2]，处理二进制位

$$\text{Trie 空间：} O(\text{总字符数} \times |\Sigma|)$$

📊 复杂度分析

💻 参考实现（C++）

#include 
using namespace std;
int trie[1000005][26], tot = 1;
bool End[1000005];
void insert(const string& s) {
    int p = 1;
    for (char c : s) {
        int ch = c - 'a';
        if (!trie[p][ch]) trie[p][ch] = ++tot;
        p = trie[p][ch];
    }
    End[p] = true;
}
bool search(const string& s) {
    int p = 1;
    for (char c : s) {
        int ch = c - 'a';
        if (!trie[p][ch]) return false;
        p = trie[p][ch];
    }
    return End[p];
}
int main() {
    int n; cin >> n;
    while (n--) {
        string op, s; cin >> op >> s;
        if (op == "insert") insert(s);
        else cout << (search(s) ? "Yes" : "No") << "\n";
    }
    return 0;
}

⚠️ 常见坑点

📚 相关题目