字典树：按前缀检索
想象你在搜索框里打字，每敲一个键就冒出一串建议。藏在背后的常常是一棵[[trie|字典树（trie）]]（读作「try」），它是一棵树，每条边是单个字符，从根出发的每条路径拼出一个前缀。共享前缀的单词会共用同一条路径，直到分叉为止。要检查某个单词是否存在，你就一次一个字符地往下走——因此一次查找花 O(L)，L 是单词长度，*与字典树里存了多少单词无关*。
Trie holding {"cat", "car", "can", "dog"}
(root)
/ \
c d
| |
a o
/ | \ |
t r n g*
* * *
(* marks the end of a real word)
Lookup "car": root -> c -> a -> r , and r is marked => found, O(3).struct TrieNode {
TrieNode* child[26] = {nullptr}; // one slot per lowercase letter
bool isEnd = false; // true if a word ends here
};
void insert(TrieNode* root, const string& w) {
TrieNode* cur = root;
for (char ch : w) {
int i = ch - 'a';
if (!cur->child[i]) cur->child[i] = new TrieNode();
cur = cur->child[i];
}
cur->isEnd = true; // mark the final node
}它的回报是前缀查询，而这正是哈希表做不好的。要为「ca」自动补全，就走到「ca」节点，再收集它下方子树里的每个单词。哈希表能告诉你「ca」是不是*恰好*为某个键，却完全不知道哪些键以「ca」*开头*。这正是字典树驱动自动补全、拼写检查和 IP 路由表的原因。
并查集：它们连通吗？
[[union-find|并查集]]（又称不相交集合结构）维护一组分组，并以惊人的速度回答一个问题：「x 和 y 在同一组吗？」它支持两种操作——union(x, y) 合并两组，find(x) 返回 x 所在组的一个代表元。当且仅当两个元素共享同一个代表元时，它们才连通。思路是：把每个组存成一棵父指针树，根充当这个组的名字。
Elements 0..5. parent[i] points up; a root points to itself.
Start: each its own group After union(0,1), union(2,3), union(1,3):
0 1 2 3 4 5 3
^ ^ ^ ^ ^ ^ / | \
(each is its own root) 1 2 (and 0 hangs under 1)
|
0
find(0) walks 0 -> 1 -> 3 ; find(2) walks 2 -> 3 ; same root => connected.两个小优化让它几乎免费。按秩合并（union by rank）总是把较矮的树挂到较高的树下，使树保持低矮。路径压缩（path compression）把 find() 过程中经过的每个节点直接重指到根上，顺带把树压平。两者合在一起，使每次操作运行在近 O(1)时间内（严格说是反阿克曼函数 α(n)，对你这辈子会遇到的任何 n，它都小于 5）。
int parent[N], rnk[N];
void init(int n){ for(int i=0;i<n;i++){ parent[i]=i; rnk[i]=0; } }
int find(int x){ // path compression
if (parent[x] != x) parent[x] = find(parent[x]);
return parent[x];
}
void unite(int a, int b){ // union by rank
a = find(a); b = find(b);
if (a == b) return;
if (rnk[a] < rnk[b]) swap(a, b);
parent[b] = a;
if (rnk[a] == rnk[b]) rnk[a]++;
}接下来该学什么
两种结构，进入了一片广阔领域。还有几个值得记住名字，这样当某个问题需要它们时你能认出来，再去查细节。它们都在回答某种形式的「快速汇总或更新一段区间的值」。