字典树（Trie）：让字符串查找变成一次 走楼梯

节点数与结构：根 R → 孩子 a（2 号）、b（6 号）；a 的孩子 b（3 号）；b（3 号）的孩子 c（4 号）、d（5 号）。

共 6 个节点（1 个根 + 5 个字符节点）。总字符数 2 + 3 + 3 + 1 = 9，但节点数只有 6，因为有 3 个字符节点被共享了。

cnt 值：cnt[R] 不计；cnt[a] = 1（只有 ab 以 a 为前缀）；cnt[ab] = 3（ab、abc、abd 都以 ab 为前缀）；cnt[abc] = 1；cnt[abd] = 1；cnt[b] = 1。

lst 为真的节点：ab（2 号的孩子）、abc、abd、b——共 4 个，恰好等于单词数 4。

关键检查：cnt[ab] = 3 是因为有 3 个单词以 "ab" 为前缀；其中 1 个（ab 自己）在节点 ab 处结束，另外 2 个（abc、abd）在它的子树里结束。验证：子树中 lst 节点数 = 3 = cnt[ab]。

易错点：插入 ab 时节点 ab 的 cnt 加了 1；随后插入 abc 时路过 ab 又加 1；插入 abd 再加 1，共 3。不要以为 "ab" 只被插入了一次。

① 查询 he：从根走 h → e，路径通畅（因为 hello/help/heap 都经过 he），所以能走到节点 he。但 lst[he] = false（"he" 本身不是词库里的单词）。所以单词查询返回 false，前缀查询返回 cnt[he] = 3。

② cnt[h] = 4——四个单词都以 h 为前缀。cnt[he] = 3——hello、help、heap 以 he 为前缀，而 hi 在第二位就分叉成了 i，不算。

③ 查询 hell：走 h → e → l → l。注意 hello 的路径是 h→e→l→l→o，所以走到第 4 个字符 "hell" 时节点存在（它是 hello 的前缀）。但 lst[hell] = false，所以返回 false（不是词），而 cnt[hell] = 1（只有 hello 经过）。

本题的训练目标：彻底分清"走得通""是词""是几个词的前缀"这三件完全不同的事。考试中大量失分都源于把这三者混为一谈。

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

const int MAXN = 100005;
int  ch[MAXN][26];
int  cnt[MAXN];
bool lst[MAXN];
int  idx = 1;

void insert(const string& s) {
    int u = 1;
    for (char c : s) {
        int v = c - 'a';
        if (!ch[u][v]) ch[u][v] = ++idx;
        u = ch[u][v];
        cnt[u]++;
    }
    lst[u] = true;
}

bool find(const string& s) {
    int u = 1;
    for (char c : s) {
        int v = c - 'a';
        if (!ch[u][v]) return false;
        u = ch[u][v];
    }
    return lst[u];
}

int countPrefix(const string& s) {
    int u = 1;
    for (char c : s) {
        int v = c - 'a';
        if (!ch[u][v]) return 0;
        u = ch[u][v];
    }
    return cnt[u];
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int n; cin >> n;
    for (int i = 1; i <= n; i++) { string s; cin >> s; insert(s); }
    int m; cin >> m;
    while (m--) {
        string s; cin >> s;
        cout << (find(s) ? "YES" : "NO") << ' ' << countPrefix(s) << '\n';
    }
    return 0;
}

自查清单：

· idx 初始化为 1 了吗？根从 1 号开始了吗？

· cnt[u]++ 写在 u = ch[u][v] 之后了吗？

· find 里返回的是 lst[u] 而不是 true 吗？

· MAXN 是按"总字符数"估的吗？（n ≤ 10⁴ 且串长 ≤ 10 时，10 万足够；但如果串长可达 100，就要开到 10⁶）

测试样例：输入 4 / ab / abc / abd / b / 5 / ab / abc / he / b / a，预期输出 YES 3 / YES 1 / NO 0 / YES 1 / NO 1。

① 错误。节点数 = 所有单词的总字符数 + 1（那个 1 是根节点，它不对应任何字符）。加上根节点才是正确的等式。

② 错误。深度相同的两个节点，如果代表相同的字符串，那它们的路径就完全相同；而从根到同一个字符串的路径是唯一的，所以它们必然是同一个节点。这正是字典树"无冲突"的本质。

③ 错误。cnt[u] > 0 只说明"有单词以 u 对应字符串为前缀"。比如只插入 abc 时，节点 a 和 ab 的 cnt 都大于 0，但 "a" 和 "ab" 都不是单词。只有 lst[u]（或 endc[u] > 0）才能判定"是单词"。

④ 错误。完全可能出现"全程走得通，但末尾不是词"的情况。例如只插入 abc，查询 ab：两位都走得通，但 lst[ab] = false。所以"断路"和"到达但不是词"是两种不同的失败方式，必须分开处理。

这四道小题的价值：它们分别对应字典树的四类经典误解——节点数公式记错、路径唯一性不理解、cnt 与 lst 混淆、失败条件不完整。把这四点澄清，字典树的判断题就再也不会错了。

标准做法（先全部插入再逐个查询）：O(n) 次插入 + O(n) 次查询，每次 O(31)，总计 O(31n)。

优化做法（边插边查）：先插入 a[1]，然后对 i = 2..n：先用 query(a[i]) 去和"已经插入的 a[1..i−1]"配对，再把 a[i] 插入。这样每个数对 (i, j)（i > j）都会在"处理 i 时"被考虑一次，一遍循环完成所有配对。

为什么等价？因为 query(a[i]) 找的是"Trie 中与 a[i] 异或最大的数"，而 Trie 中恰好是 a[1..i−1]。每一对 (i, j) 在 i 被处理时贡献一次候选，全部覆盖。

好处：代码更短，只需一次循环；内存上 Trie 节点逐步增长，缓存更友好（实测大约快 20%~30%）。唯一注意点：要保证 i ≥ 2 才有东西可查，且 n = 1 时答案是 0（或按题意特殊处理）。

代码骨架：insert(a[1]); int ans = 0; for (i = 2; i <= n; i++) { ans = max(ans, query(a[i])); insert(a[i]); }

对比暴力法：O(n²) 枚举点对，n = 10⁵ 时是 10¹⁰ 次运算，必然超时。01-Trie 把它降到 3 × 10⁶。

先看清方向的差别：前面学的 countPrefix(s) 求的是"以 s 为前缀"；本题求的是"是 s 的前缀"。这是两个完全不同的问题。

做法：仍然把 n 个单词建成字典树。查询时，从根开始沿着 s 的字符一路下走，沿途累加每个节点的 lst 计数（即"在这个位置结束的单词数"）。走到 s 结束（或者中途断路），累加值就是答案。

为什么？s 的前缀恰好是 s 的每一个"路径前段"。一个单词 w 是 s 的前缀，当且仅当 w 的路径是 s 路径的一段前缀，也就是 w 的结束节点在 s 的路径上。所以把 s 路径上所有节点的 endc 加起来就是答案。

核心代码：把查询改成
int res = 0, u = 1; if (endc[1]) res += endc[1]; // 空串特判
for (char c : s) { int v = id(c); if (!ch[u][v]) break; u = ch[u][v]; res += endc[u]; }
return res;

易错点一：必须边走边累加，而不是走到末尾再读一个值。易错点二：如果允许空串作为单词（少见），根节点的 endc 也要计入。易错点三：中途断路时要 break 而不是 return 0——因为断路之前已经累加的答案是有效的！

对比记忆："以 s 为前缀" → 走完 s，读 cnt[u]（一个点）；"是 s 的前缀" → 走 s 的过程中，累加 endc（一条路径）。方向不同，读法完全不同。

解法一（暴力两两求 LCP）：O(n² × L)，n = 10⁴ 时不可接受。

解法二（字典树，推荐）：把所有单词插入字典树后，从根出发一直往下走，只要当前节点满足"cnt[u] == n"（即所有 n 个单词都经过它）且"只有一个孩子"，就继续往下走。走到不能再走时，路径上的字符数就是最长公共前缀的长度。

为什么？首先，公共前缀必须被所有单词共享，所以它的每个节点都需要 cnt[u] == n。其次，如果在某个节点出现了两个以上的不同孩子，就说明单词在这一点开始分叉，公共前缀到此为止。

还要注意一个细节：如果某个单词在分叉点之前就结束了呢？例如单词集合是 {a, ab}，那么 cnt[a节点] = 2，只有一个孩子 b，能继续走到 ab；但此时 cnt[ab] = 1 ≠ 2，说明不是所有单词都经过，停在这里。答案应该是 a（因为 a 是其中一个单词，公共前缀不能超过最短单词）。所以循环条件要写成：cnt[u] == n 且 endc[u] == 0（当前节点不是任何单词的结尾）且只有一个孩子。

复杂度：建树 O(总字符数)，之后沿树往下走最多 O(最长单词长度)，合计 O(总字符数)。

边界情况：n = 0 或 n = 1 时要特判；若某个单词是空串，最长公共前缀显然也是空串。若所有单词都有不同的首字母，答案是空串（长度 0）。

内存评估：2 × 10⁶ × 52 × 4 字节 = 416 MB。远超常见的 256 MB 限制，必然 MLE。

方案一：改用 map 或哈希表存孩子。map<char,int> ch[MAXN]——只为真实存在的边分配。实际中每个节点的平均孩子数远小于 52（通常 1~3 个），所以能省 90% 以上的内存。代价是每次访问 O(log k)，常数大增，可能 TLE。折中方案：用 unordered_map 或手写哈希，把 O(log k) 降到 O(1)。

方案二：邻接表（链式前向星）。用 head[u]、nxt[e]、to[e]、cch[e] 四个数组存边，每条边只占几个 int。总边数 = 节点数 − 1（树的性质！），所以空间是 O(节点数) 而不是 O(节点数 × 52)。这是最推荐的方案。查孩子时要遍历链表，但因为每个节点的孩子数很少，实际非常快。

方案三：压缩字符集。实际上 52 种字符未必都在同一层出现。可以给每个节点单独建"字符到孩子的映射"，或者把出现频率高的字符放在前面，用"线性扫描 + 提前终止"。

方案四：改用 vector<pair<char,int>>。C++ 的 vector 有 24 字节开销（指针 × 3），2 × 10⁶ 个节点就是 48 MB 的纯开销，反而可能更差。相比之下邻接表的固定数组更省。

方案五：bitset 辅助快速判断。为每个节点维护一个 52 位的掩码，快速判断"某字符的孩子是否存在"，再用数组存真实孩子。

结论排序：邻接表（最省、推荐） > 手写哈希 > unordered_map > map。选择时看"时间限制"和"数据特征"，如果平均孩子数很低，邻接表几乎无损。

答案：可持久化 01-Trie。这是本讲拓展案例 1 的应用，也是 01-Trie 最重要的高级用法。

第一步：建立版本。令 root[i] 表示把 a[1]、a[2]、…、a[i] 依次插入后的 Trie 根。插入 a[i] 时，沿路径复制节点：路径上每个节点都新建一份，未走的兄弟子树直接指向旧版本的节点。这样 root[i] 到 root[i-1] 只多了 O(log V) 个新节点。

第二步：记录 latest。每个节点上存一个 latest[u]，表示"最后一次经过这个节点的下标"。新建节点时把它设为当前下标。

第三步：查询 [l, r] 与 x 异或最大值。从 root[r] 出发，按位从高到低。每一步想做贪心取反时，判断条件是：目标孩子存在，且 latest[目标孩子] >= l。满足才走；否则只能走原孩子。

为什么 latest ≥ l 就够？因为 root[r] 这个版本里包含的所有数的下标都 ≤ r。若某个分支的 latest ≥ l，说明至少有一个下标 ≥ l 的数走过这条分支，于是这个分支里就存在下标在 [l, r] 内的数。两个条件合起来正好圈定区间。

第四步（本题的双数版本）：询问是"区间内选两个数异或最大"。做法是：枚举 i 从 l 到 r，对每个 i 求"在 [l, r] 中与 a[i] 异或最大的数"，取最大值。但这样是 O(len × log V)，不够快。

优化：其实可以只查一次——对固定的 i，最优配对只会是"全局区间 [l,r] 中与某个 a[i] 异或最大的"。更常见的做法是：把问题转化成"求前缀异或序列中的两个数"，如果是"区间异或和最大"（即 d[r] xor d[l-1] 的推广），可以用可持久化 01-Trie 直接在区间内做整体贪心。具体做法：在可持久化 01-Trie 上同时维护两个指针（表示要选的两个数的路径），做"双指针贪心"，每一步尽量让两条路径在这一位上不同。这类做法在 P4735、P5283 等题中出现。

空间警示：n = 3 × 10⁵、位数 31，节点数 = n × 31 ≈ 9.3 × 10⁶，ch[MAXN][2] 需 9.3 × 10⁶ × 2 × 4 ≈ 75 MB，加上 root[] 与 latest[] 略显吃紧。开数组前一定要算清。

能，而且非常简单——这几乎是字典树"免费"提供的能力。

做法：从根出发沿 s 逐字符下走。每走成功一步，就把"当前已走的长度"记下来作为候选答案。一旦某一步 ch[u][v] == 0（走不动了），立即停止。此时"成功走过的最大长度"就是答案。

核心代码：
int u = 1, best = 0;
for (int i = 0; i < (int)s.size(); i++) {
  int v = id(s[i]);
  if (!ch[u][v]) break;
  u = ch[u][v]; best = i + 1;
}
return best;

复杂度 O(L)，与词库大小无关。这正是字典树"路径即前缀"这一性质带来的天然红利。

推广一下：如果题目要求"找出那个具体的单词"，只需在走到最后一个可行节点后，从该节点向下 DFS 找任意一个词尾节点即可（DFS 到 lst 为真的节点就返回）。

对比哈希表：哈希表要解决这个问题，只能枚举所有可能的 L 个前缀去查哈希表，每次 O(L) 计算哈希，总计 O(L²)。而字典树是 O(L)。当 L = 10⁵ 时，L² 与 L 的差距是 10⁵ 倍——这就是"保留内部结构"的威力。

实际应用：这个能力正是输入法、搜索引擎自动补全、IDE 代码提示的底层原理——它们维护了一棵巨大的字典树，用户每敲一个字符就沿树走一步，走不动了就说明没有补全候选。

情形一：允许相同下标（即等价于求"某个数本身"）。三数异或允许重复下标时，问题退化成"在 {a[i] xor a[j]} 集合里再异或一个 a[k]"，可以枚举 i、j 得到 n² 个数再建 Trie，复杂度 O(n² log V)，n ≤ 5000 时可行。

情形二：要求三个不同下标。这是个困难问题，没有 O(n log V) 的通用解法。常见思路有：

思路 A（随机化 / 迭代加深）：从高位到低位逐位确定答案。设当前已确定的高位前缀为 P，我们要判断"是否存在三个不同下标的数，异或后的高位等于 P 且某一位能取 1"。判断本身仍需要搜索，通常配合"按高位分组 + 组内枚举"来做，最坏复杂度仍然很高。

思路 B（线性基，但只能处理"子集异或"）：线性基能干的是"从 a 中选一个子集，使异或和最大"。这允许任意多个数，也允许重复使用下标（因为下标选不选是 0/1 决策）。所以如果题目允许"选若干个数"，线性基是正解；但若限定"恰好三个不同下标"，线性基不适用。

思路 C（Meet in the middle）：枚举所有 a[i] xor a[j]（i ≠ j），存进 01-Trie，再枚举 k 查询。复杂度 O(n² log V)，且要去重防下标冲突。n ≤ 3000 左右可行。

关键启示：这题的价值在于让你体会"问题的精确措辞会彻底改变算法"。"选两个数"→ 01-Trie；"选任意多个数"→ 线性基；"恰好三个不同下标"→ 没有简单解法。竞赛中读题时必须把这些限定条件逐字确认。

本讲范围内的正确回答：对于"恰好两个数异或最大"，答案是 01-Trie，O(n log V)；对于更复杂的组合约束，需要具体问题具体分析，本讲不作展开。

能，前提是这些数按"从高位到低位"建 Trie，并在每个节点上记录子树中的元素个数 sz[u]。

做法（求第 k 大）：从根出发，按位从高到低。设当前节点为 u，我们希望走"较大的那个分支"。若这棵树是"0 左 1 右"，那么右边的子树（1 分支）里的数更大。

· 令 R = sz[ch[u][1]]（右子树大小）。
· 若 k <= R：第 k 大的数在右子树里，走右边，这一位是 1。
· 否则：第 k 大的数在左子树里，走左边，k -= R，这一位是 0。

走到叶子（或者走满位数）时，路径上的 0/1 拼起来就是第 k 大的数。复杂度 O(log V)。

关键区别一：索引方式。权值线段树/树状数组的下标本身就是"值的排名信息"，左子树管 [l, mid]、右子树管 [mid+1, r]，是按值域二分。而 01-Trie 是按二进制位分层——第 1 层区分"最高位是 0 还是 1"，第 2 层区分"次高位"。两者的"大小关系"与"树形结构"的对应方式不同，但本质都是"用树的形状编码大小"。

关键区别二：支持的动态操作。01-Trie 插入/删除一个数要改动 O(log V) 个节点的 sz，和 BIT 一样。但 01-Trie 的优点是易于可持久化（路径复制天然适合），而 BIT 的可持久化（主席树）需要用权值线段树而不是 BIT。

关键区别三：值域依赖性。01-Trie 的层数固定为位数（如 31），与值域的具体大小无关；权值线段树/树状数组的层数是 O(log(值域))，对值域 10⁹ 时需要动态开点或离散化。01-Trie 天然支持稀疏的大值域。

一句话总结：01-Trie 是"按位二分值域"的权值树，它和权值线段树是同一思想的两种索引方式。学会 01-Trie 后，理解主席树、线段树合并都会顺畅很多——因为它们都在做同一件事：在一棵按值域组织的树上，用子树大小做定位。