字典樹：按前綴檢索
想像你在搜尋框裡打字，每敲一個鍵就冒出一串建議。藏在背後的常常是一棵[[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]++;
}接下來該學什麼
兩種結構，進入了一片廣闊領域。還有幾個值得記住名字，這樣當某個問題需要它們時你能認出來，再去查細節。它們都在回答某種形式的「快速彙總或更新一段區間的值」。