Tree · 比較表
樹狀資料結構比較
BST、平衡樹、字典樹、線段樹、Fenwick 樹：各自支援哪些操作、能不能改、什麼問題該用哪一棵。
| 演算法 | 時間 | 空間 | 鍵 | 核心操作 | 可修改 | 難度 |
|---|---|---|---|---|---|---|
| BST二元搜尋樹 | O(h) | O(h) | 可比較的值 | 查、插、刪、前驅後繼 | ✓ | 進階 |
| Balanced BST平衡樹概念 | O(log n) | O(n) | 可比較的值 | BST 全部，保證 O(log n)；範圍查詢、第 k 小 | ✓ | 困難 |
| Trie字典樹 | O(L) | O(ΣL) | 字串的每個字元 | 插入、查詞、查前綴 | ✓ | 進階 |
| Segment Tree線段樹 | O(log n) | O(n) | 陣列索引 | 區間查詢（和、最大、最小、任何可合併的）、單點或區間更新 | ✓ | 困難 |
| Fenwick Tree (BIT)樹狀陣列 | O(log n) | O(n) | 陣列索引 | 前綴和、單點更新 | ✓ | 困難 |
什麼時候選哪一個
BST 二元搜尋樹
教學與面試：理解「有序 + 動態」怎麼做到 O(h)。實務上不會自己寫不平衡的 BST。
Balanced BST 平衡樹概念
需要「有序集合」而且會一直增刪：C++ `map`／`set`、Java `TreeMap`。雜湊表做不到「比 k 大的最小值」時就是它。
Trie 字典樹
前綴才是重點：自動補全、以前綴計數、最長公共前綴、位元字典樹求最大 XOR。
Segment Tree 線段樹
區間查詢 + 更新，而且查的不只是和（最大值、GCD、區間賦值需要懶標記）。功能最全、程式最長。
Fenwick Tree (BIT) 樹狀陣列
區間和 + 單點更新，只要這兩樣：十行寫完、常數比線段樹小。逆序對計數、動態排名的首選。
選擇指南
- 有序 + 動態增刪 → 平衡樹（用內建的）。只查在不在 → 雜湊表更快。資料不變 → 排序陣列 + 二分就夠。
- 區間和、資料不變 → 前綴和（O(1) 查）。區間和、會改 → Fenwick。區間最大／最小、會改 → 線段樹。
- 區間更新（整段加值、整段賦值）→ 線段樹加懶標記。Fenwick 只能做「區間加、單點查」這一種變形。
- 鍵是字串且問前綴 → 字典樹。鍵是字串但只問相等 → 雜湊表，字典樹沒有優勢。
- 第 k 小、排名 → 平衡樹（帶子樹大小）或值域上的 Fenwick 樹，後者在值域可離散化時更好寫。