Learning Objectives
- 說明只存原陣列與存前綴和各自的取捨：一個查詢慢、一個修改慢
- 說出線段樹每個節點存什麼、怎麼用陣列存（根在 1，子節點 2k、2k + 1），並追蹤建樹的過程
- 追蹤線段樹的區間查詢（不重疊、完全包含、部分重疊三種情況）與單點修改，說明兩者都是 O(log n)
- 用 lowbit（i & -i）說明 Fenwick 樹每一格管哪一段，追蹤前綴查詢與修改的跳躍
- 依需要的運算與實作成本，在前綴和、線段樹、Fenwick 樹之間做選擇
區間總和與修改都要快
一家店把每天的營業額存在陣列 a 裡，常有兩種要求：
- 區間查詢：「第 l 天到第 r 天一共賣了多少？」也就是
a[l] + a[l+1] + … + a[r] - 單點修改：「第 i 天的數字記錯了，改成 x。」
只做其中一種很簡單，難的是兩種交錯而且次數都很多：例如即時的排行榜、一直有新資料進來的感測紀錄、 程式競賽裡十萬次查詢夾著十萬次修改。這一課從兩種直覺的做法開始，看它們卡在哪裡，再做出讓兩種操作都是 O(log n) 的兩種結構： 線段樹（segment tree）與 Fenwick 樹（也叫樹狀陣列、binary indexed tree）。
這一課的陣列一律是 8 個元素：a = [5, 2, 7, 1, 8, 3, 6, 4]，區間用 a[l..r] 表示，含兩端。
原陣列與前綴和：各快一半
前半段比較兩種查詢：原陣列要把 a[2]～a[6] 五格加起來；前綴和只要 pre[7] - pre[2]，看兩格。後半段把 a[3] 加 10：原陣列改一格就好，前綴和卻要把 pre[4] 到 pre[8] 全部改掉，因為它們都包含 a[3]。
兩種做法卡在哪裡
| 區間查詢 | 單點修改 | |
|---|---|---|
| 只存原陣列 | O(n) | O(1) |
| 存前綴和 | O(1) | O(n) |
| 線段樹 | O(log n) | O(log n) |
| Fenwick 樹 | O(log n) | O(log n) |
n = 100,000、查詢與修改各 100,000 次時，前兩種做法總共要約 100 億次運算；後兩種每次約 17 步（log₂100,000 ≈ 17）， 總共約 340 萬次。
前綴和慢在「一個元素被太多格包含」：a[0] 出現在每一個 pre 裡，改它就要改 n 格。 原陣列慢在「每一格只包含一個元素」，查詢要一格一格加。中間的做法是：預先算好一些長短不一的區段的和， 讓每個元素只被 log n 個區段包含（修改快），任何區間又都能拼成 log n 個區段（查詢快）。線段樹與 Fenwick 樹是兩種切法。
線段樹的結構
線段樹是一棵二元樹，每個節點存一段區間的總和：
- 根管整個陣列
a[0..7] - 管
a[lo..hi]的節點，左子節點管前半a[lo..mid]，右子節點管後半a[mid+1..hi]，mid = (lo + hi) / 2 - 一直切到只剩一個元素，就是葉節點
和堆積一樣，線段樹用陣列存，不用節點物件（第 14 課的堆積是從索引 0 開始，這裡從 1 開始比較好算）：
| 位置 | |
|---|---|
| 根 | tree[1] |
| 節點 k 的左、右子節點 | tree[2k]、tree[2k + 1] |
| 節點 k 的父節點 | tree[k / 2]（整數除法） |
n 是 2 的次方時，一共 2n - 1 個節點，陣列開 2n 格（tree[0] 不用），葉節點 a[i] 剛好在 tree[n + i]。
n 不是 2 的次方時，樹的最後一層不會排滿，習慣上開 4n 格保證夠用。
建樹用遞迴：先建好兩個子節點，自己的值就是兩個子節點相加。每個節點只算一次，建樹是 O(n)。
建線段樹：先建子節點，再把兩段加起來
樹的形狀和堆積相同，只是每個節點存的是「一段的總和」。注意建造的順序：遞迴先一路往左走到葉節點 a[0]，葉節點填好之後才回頭算父節點，所以樹是由下往上填滿的。最後 tree[1] 是整個陣列的總和 36。
區間查詢：三種情況
查 a[l..r] 的總和，從根開始問。目前的節點管 a[lo..hi]，和查詢範圍的關係只有三種：
| 情況 | 條件 | 做法 |
|---|---|---|
| 完全不重疊 | r < lo 或 hi < l |
這一段用不到，回傳 0 |
| 完全包含 | l <= lo 且 hi <= r |
整段都要，直接回傳 tree[node]，不再往下 |
| 部分重疊 | 其他 | 問兩個子節點，把答案加起來 |
查詢範圍最後被拆成幾個「完全包含」的節點，例如 a[2..6] 拆成 a[2..3]、a[4..5]、a[6..6] 三段。
為什麼是 O(log n)：在樹的每一層，「部分重疊」的節點最多只有兩個，也就是包著查詢範圍左端點和右端點的那兩個； 其他節點不是整段在裡面，就是整段在外面，會在它們的父節點那一層就停下來。所以每一層最多拜訪約 4 個節點， 樹高 log₂n，總共 O(log n)。
區間查詢：拆成幾段拿來用
比較 ▲ lo、hi 和亮起來的查詢範圍：整段落在範圍裡就直接用（輸出會印出用了哪一個節點）；完全在外面就回傳 0；只有一部分重疊才往下問。查 a[2..6] 用了 3 個節點，查 a[0..5] 只用 2 個：tree[2] 一次就給了 a[0..3]。
單點修改：從葉節點往上重算
改一個元素，只有「管到它」的節點要跟著變：就是從它的葉節點到根的那一條路徑，每一層一個，一共 log₂8 + 1 = 4 個。因為 n = 8 是 2 的次方，a[i] 的葉節點就在 tree[8 + i]，往上走就是一直除以 2。
線段樹還能做什麼
範例用的「從葉節點往上走」只在 n 是 2 的次方、而且樹照這個方式排列時成立；一般的 n 用和查詢一樣的遞迴寫法： 往包含 i 的那一半走下去，改完葉節點，回來的路上重算每個節點。成本一樣是 O(log n)。
節點存的不一定是總和。只要合併兩段的運算滿足結合律（先合併哪兩段，結果都一樣），線段樹都能用：
| 節點存什麼 | 合併方式 | 回答的問題 |
|---|---|---|
| 總和 | 左 + 右 | 區間和 |
| 最小值 | min(左, 右) | 區間最小值（例如一段時間裡的最低氣溫） |
| 最大值 | max(左, 右) | 區間最大值 |
| 最大公因數 | gcd(左, 右) | 區間的最大公因數 |
「不重疊」時回傳的值要換成這個運算的單位元素：加法是 0，最小值是無限大，最大值是負無限大。
另外還有區間修改（例如「a[2..6] 全部加 5」）的需求，做法是在節點上記下「這一段還欠子節點多少沒加」，等真的需要往下走時才補上， 叫做延遲標記（lazy propagation），屬於進階內容，這裡不展開。
想一想：線段樹
用這一課的線段樹（n = 8，根是 tree[1]）查 a[0..7] 的總和，會拜訪幾個節點？
把 a[5] 改掉之後，線段樹裡哪些節點要重算（n = 8，葉節點 a[i] 在 tree[8 + i]）？
想用線段樹回答「a[l..r] 裡最大的值」，查詢遇到「完全不重疊」的節點時應該回傳什麼？
Fenwick 樹：用二進位決定每一格管哪一段
Fenwick 樹由 Peter Fenwick 在 1994 年發表，原本用在資料壓縮裡維護累積次數表。它只用一個長度 n + 1 的陣列 bit，索引從 1 開始（bit[0] 不用），
第 i 個元素就是 a[i - 1]。
關鍵是 lowbit(i)：i 的二進位裡最低的那個 1 所代表的值。例如 6 是 110，最低的 1 在 2 的位置，lowbit(6) = 2。
bit[i] 存的是「第 i - lowbit(i) + 1 個到第 i 個」的總和，也就是以 i 結尾、長度 lowbit(i) 的一段：
| i | 二進位 | lowbit(i) | bit[i] 管 | 值（a = 5 2 7 1 8 3 6 4） |
|---|---|---|---|---|
| 1 | 0001 | 1 | 第 1 個 | 5 |
| 2 | 0010 | 2 | 第 1～2 個 | 7 |
| 3 | 0011 | 1 | 第 3 個 | 7 |
| 4 | 0100 | 4 | 第 1～4 個 | 15 |
| 5 | 0101 | 1 | 第 5 個 | 8 |
| 6 | 0110 | 2 | 第 5～6 個 | 11 |
| 7 | 0111 | 1 | 第 7 個 | 6 |
| 8 | 1000 | 8 | 第 1～8 個 | 36 |
兩個操作：
- 前綴查詢（第 1 個到第 i 個的和）：加上
bit[i]，然後i -= lowbit(i)，跳到前一段的結尾，直到 i 變成 0。 例如 i = 7：bit[7]（第 7 個）+bit[6]（第 5～6 個）+bit[4]（第 1～4 個）。每跳一次去掉一個 1 位元，最多 log₂n 次。 - 修改（第 i 個加 delta）：
bit[i]加 delta，然後i += lowbit(i)，跳到下一個也管到第 i 個的格子，直到超過 n。 例如 i = 3：bit[3]→bit[4]→bit[8]。
lowbit 在程式裡寫成 i & -i。整數用二補數表示，-i 等於「i 的每個位元反轉再加 1」，反轉之後最低的 1 以下全是 1，
加 1 一路進位到原本最低的 1 那一格；和 i 做 AND，只剩那一個位元。Python、C++、Java 對正整數算出的結果相同。
區間和用兩次前綴查詢相減：a[l..r] 的和 = 前 r + 1 個的和 − 前 l 個的和。
Fenwick 樹：建立、查詢、修改
建立時把 8 個元素一個一個「加進去」：例如第 1 個元素的 5 會加到 bit[1]、bit[2]、bit[4]、bit[8]，因為這四格都管到第 1 個。接著查 a[2..6]：前 7 個的和走 7 → 6 → 4，前 2 個的和走 2，相減得到 25。最後 a[3]（第 4 個）加 10，只改 bit[4]、bit[8] 兩格。
線段樹與 Fenwick 樹怎麼選
| 前綴和陣列 | 線段樹 | Fenwick 樹 | |
|---|---|---|---|
| 額外空間 | n + 1 | 2n～4n | n + 1 |
| 建立 | O(n) | O(n) | O(n log n)（逐一加入；也有 O(n) 的建法） |
| 區間和 | O(1) | O(log n) | O(log n)（兩次前綴相減） |
| 單點修改 | O(n) | O(log n) | O(log n) |
| 程式長度 | 最短 | 較長（遞迴、三種情況） | 很短（兩個迴圈） |
| 區間最小值、最大值 | 不行 | 可以 | 不能直接做 |
Fenwick 樹回答區間和靠的是「前 r + 1 個 − 前 l 個」，需要能把多加的部分減回去；最小值沒有「減法」， 所以 Fenwick 樹不能直接查區間最小值。線段樹只需要結合律，用途比較廣。
選擇的原則：
- 資料不會修改：前綴和就好，查詢 O(1)
- 只要區間和（或其他可以減回去的運算，例如次數、互斥或）且有修改：Fenwick 樹，程式短、記憶體少
- 要區間最小值、最大值，或之後還要擴充（區間修改、存更多資訊）：線段樹
想一想：lowbit 與跳躍
下面的程式印出什麼？
for i in [6, 8, 12]:
print(i & -i, end=" ")
Fenwick 樹有 n = 16 格。對第 5 個元素做修改，會依序更新哪些格子？
題目只要求「區間最小值」，而且陣列會被修改。用哪一種結構最直接？
實作：Fenwick 樹的查詢與「改成某個值」
add 已經寫好。請完成兩個函式：prefix(bit, i) 回傳第 1 個到第 i 個的和；set_value(bit, a, n, i, x) 把 a[i] 改成 x，Fenwick 樹只會「加」，所以要先算出差了多少，再呼叫 add，最後別忘了把 a[i] 也改掉。
重點整理
- 只存原陣列：查詢 O(n)、修改 O(1)；存前綴和：查詢 O(1)、修改 O(n)。查詢與修改交錯很多次時都太慢
- 線段樹：每個節點存一段的和，用陣列存（根
tree[1]，子節點2k、2k + 1）；建樹 O(n)，查詢把區間拆成 O(log n) 個節點，修改重算葉節點到根的 log n + 1 個節點 - 查詢的三種情況：不重疊回傳單位元素、完全包含直接用、部分重疊問兩個子節點；只要運算有結合律（和、min、max、gcd）都能用
- Fenwick 樹：
bit[i]管以 i 結尾、長度 lowbit(i) =i & -i的一段；查詢i -= lowbit(i)、修改i += lowbit(i)，都是 O(log n)，程式短、只多 n + 1 格 - 區間和用兩次前綴相減，所以 Fenwick 樹不能直接查區間最小值
下一課：LRU 快取。把雜湊表和雙向鏈結串列組合起來，讓兩個操作都是 O(1)，最後整理整個資料結構軌的選擇方法。