字典树（Trie）

支持 \(O(|s|)\) 插入/查询一个字符串。空间复杂度为 \(O(|s|_{\max}|\Sigma|)\)。

01 Trie

即 \(\Sigma=\{0,1\}\) 的字典树，类似二进制，插入/查询一个数复杂度为 \(O(\log x)\)。空间复杂度貌似是 \(O(\log x)\) 的？

这种数据结构可以用来维护异或等基本操作，由于不需要递归，所以常数会小些。

维护异或极值

例：P4551 最长异或路径

给你一棵树，树上每个点有点权，求 \((u,v)\) 满足路径上的边权异或值最大。
\(n\le 10^5,w\in[0,2^{31})\)

记 \(X(u,v)\) 为 \((u,v)\) 路径上的异或和，钦定 1 为根。考虑异或有性质 \(X(u,v)=X(u,1)\oplus X(v,1)\)，考虑记下每个 \(X(u,1)\) 并插入 01 Trie，然后对于每个 \(u\)，从 01 Trie 的根开始找尽量与 \(X(u,1)\) 当前位不同的位跑，直到走到底。显然越高位的贡献越大（\(2^{x}>2^{x-1}+2^{x-2}+\ldots+1\)），所以贪心正确。