第8章 進階樹結構#

本章目標#

• 實作 Trie（字典樹），掌握前綴類問題的解法。
• 理解線段樹如何做到 O(log n) 的區間查詢與更新。
• 學會樹狀陣列（BIT / Fenwick Tree）的前綴和技巧。

章前言#

當問題從「找一個鍵」變成「找一群有共同特徵的鍵」或「查一段區間的統計」，一般搜尋樹就力不從心了。本章介紹三種「為特殊問題特化」的樹結構——它們也是「資料結構設計思維」最好的教材：針對操作模式剪裁結構，效率就會脫胎換骨。

Trie（字典樹 / 前綴樹） 把字串按字元一層層掛下去，共用共同前綴。查一個單字的成本只與「字長」有關（與字典大小無關），而且天然支援「所有以 abc 開頭的單字」這類前綴查詢——搜尋引擎的自動補全、拼字檢查、IP 路由都靠它。

線段樹（segment tree） 把陣列切成一段段區間存進樹中，區間查詢（如「區間和、區間最大」）與單點更新都是 O(log n)。若用樸素方法，更新 O(1) 但區間查詢 O(n)，反覆查詢時慢得難以忍受。

樹狀陣列（Binary Indexed Tree / Fenwick Tree） 是線段樹的精簡版：只處理「前綴和」類可逆運算，程式碼只有十行，靠索引的二進位補碼技巧在 O(log n) 內完成前綴和與更新。線段樹功能強大，BIT 輕巧夠用——兩者的取捨本身就是好教材。