前綴和能算靜態區間和，改一個元素就要重建。堆積只會取極值，不會做「區間和」。線段樹與樹狀陣列補上的是：陣列會改，又要很快問區間。NTUCPC 這類大綱把兩者放在基礎資料結構的後段；本站先前沒有獨立教材。
相關教材：Heap_Priority_Queue_Teaching_Materials.md、本篇後面的前綴和若需要靜態版本，見 Prefix_Sum_Two_Pointers_Teaching_Materials.md。
目錄
1. 靜態前綴和為什麼不夠
陣列 a = [2, 1, 4, 3]。前綴和可以 (O(1)) 回答區間和，但把 a[1] 改成 5 之後，後面的前綴全部要重算，單次修改 (O(n))。
若修改和查詢交錯 (q) 次，朴素做法是 (O(nq))。線段樹把兩種操作都做成 (O(\log n))。
能做的不限於和。任何有結合律、有單位元的運算都可以放在節點上：和、最小、最大、gcd、矩陣乘積。沒有結合律（例如「區間中位數」）就不能用這個骨架。
2. 線段樹的區間
把 ([0, n)) 切成一棵二元樹。節點 (v) 代表半開區間 ([L, R))。
- 葉子：(R = L+1)，存
a[L]。 - 內部節點：中點 (M=\lfloor (L+R)/2 \rfloor)，左孩子 ([L, M))，右孩子 ([M, R))，節點的值是左右的和。
(n=4) 時：
[0,4) = 10
/ \
[0,2)=3 [2,4)=7
/ \ / \
[0,1) [1,2) [2,3) [3,4)
2 1 4 3查詢區間若剛好等於某個節點，直接回傳。否則拆成左右兩段，最多碰到 (O(\log n)) 個節點。這是線段樹時間的原因：每一層最多貢獻兩個「懸空」的節點。
3. 建樹、單點更新、區間查詢
建樹是後序：先孩子再自己，(O(n))。
單點更新：從根走到那片葉子，改值，沿路重算父親，(O(\log n))。
區間查詢 ([ql, qr))：
- 與節點區間不相交：回傳 0（和的單位元）。
- 節點區間完全落在查詢裡：回傳節點值。
- 否則兩邊遞迴再相加。
把 a[1] 從 1 改成 5。葉子 ([1,2)) 變成 5，父親 ([0,2)) 變成 (2+5=7)，根變成 (7+7=14)。新的全陣列和是 (2+5+4+3=14)。
4. 手算
查 ([1, 3))，也就是 1+4=5（修改之前）。
根 ([0,4)) 只有一部分被問到。
- 左 ([0,2))：只要 ([1,2))，得到 1。([0,1)) 在查詢外面。
- 右 ([2,4))：只要 ([2,3))，得到 4。([3,4)) 在外面。
相加是 5。沒有把整段 ([0,2)) 的 3 拿來用，因為查詢不包含索引 0。
5. 懶標記：區間加值
「把 ([L, R)) 每個元素加 (d)」若走下去改每一片葉子，最壞是 (O(n))。
懶標記：節點若完全被加值區間蓋住，就只更新這個節點的和（加上 (d) 乘上區間長度），並把 (d) 記在節點上，先不傳給孩子。之後真的要走進這個節點時，再把標記推下去。
不變量：節點的和是正確的；標記表示「孩子們都還沒加上的值」。推下去之後，孩子的和也變正確，自己的標記清成 0。
例：對 ([1, 3)) 加 1。原陣列變成 [2, 2, 5, 3]，總和 12。查全區間應得到 12，查 ([1, 3)) 應得到 (2+5=7)。
標記只寫在被完整蓋住的節點上。部分重疊的節點自己不加標記，只是把左右的結果加起來。
這個技巧依賴「加值對和的影響可以只看區間長度算出」。若改成「區間設成同一個值」或「區間取 min」，標記的合併規則要重寫，不能沿用「加上 (d\times)長度」。
6. 樹狀陣列
樹狀陣列（Binary Indexed Tree、Fenwick tree）用一個陣列模擬「每個索引負責一段長度為 2 的冪的前綴」。索引從 1 開始比較不容易寫錯。
i 負責的長度是 i 的最低位 1，也就是 i & -i。
更新索引 i（加一個值）：反覆 i += i & -i，沿路加上去。
前綴和到 i：反覆 i -= i & -i，沿路相加。
區間 ([l, r]) 的和是 prefix(r) - prefix(l-1)。
同一份資料 2, 1, 4, 3 放在 1-based 索引 1..4。依序更新之後：
| 索引 | bit 值 | 它代表的原陣列和 |
|---|---|---|
| 1 | 2 | a1 |
| 2 | 3 | a1+a2 |
| 3 | 4 | a3 |
| 4 | 10 | a1+...+a4 |
prefix(3) = bit[3] + bit[2] = 4+3 = 7，即 2+1+4。prefix(3)-prefix(1) = 5，即索引 2 到 3 的 1+4。
時間 (O(\log n))，空間 (O(n))，常數比線段樹小，程式也短。它自然支援的是「前綴」以及能由前綴相減得到的區間和。區間加值、區間查詢同時要做，或運算不是可逆的（區間 min），線段樹比較直接。
7. 兩者怎麼選
| 需求 | 選擇 |
|---|---|
| 單點改、前綴和或區間和 | 樹狀陣列，程式短 |
| 區間 min / max / gcd | 線段樹 |
| 區間修改 + 區間查詢 | 線段樹加懶標記 |
| 靜態陣列、只有查詢 | 前綴和，不必建樹 |
| 只要全域最小、還會插入刪除 | 堆積，不是線段樹 |
(n) 若不是 2 的冪，兩種結構都不用先補齊到 2 的冪再當特殊情況。線段樹用半開區間切到葉子即可；樹狀陣列的長度設成 (n) 即可。
8. 常見陷阱
- 閉區間和半開區間混用。 本篇線段樹是 ([L, R))。查詢右端多 1 會多加一個元素。
- 樹狀陣列用 0 當索引。
i & -i在i=0是 0，迴圈不會前進。索引請從 1 開始，或在外面平移。 - 懶標記忘了先推再遞迴。 孩子的和還是舊的，查詢會少加。
- 非結合運算。 區間中位數不能由左右中位數算出。
- 更新寫成加，查詢卻把葉子設成绝对值。 單點「設值」和單點「加值」的葉子操作不同，父親才是重新求和。
- 整數溢位。 區間和用 32 位元整數，(n) 與值一大就溢位。和請用 64 位元。
9. 練習題
- 陣列
[2, 1, 4, 3]，線段樹查 ([0, 3)) 應回傳多少？會用到哪些葉子？ - 把索引 3 的 3 改成 0 之後，根的值是多少？
- 用第 6 節的
bit，計算prefix(2)與索引 2..4 的區間和。 - 為什麼區間最小值不能用「兩個前綴最小值相減」做在樹狀陣列上，卻可以做在線段樹上？
- 懶標記區間加值時，節點和要加
d還是d * 區間長度？
參考答案
2+1+4=7。葉子是 ([0,1))、([1,2))、([2,3))。其中 ([0,2)) 可以整段取用（值 3），不必拆開；([2,3)) 單獨取 4。- 總和少 3，根從 10 變成 7。
prefix(2)=bit[2]=3。索引 2..4 的和是prefix(4)-prefix(1)=10-2=8，即1+4+3。- 最小值沒有反運算，前綴 min 相減沒有意義。線段樹的節點存的是該段的 min，查詢時對覆蓋節點取 min，不需要相減。
- 加
d * 區間長度。標記本身只存d，因為每個元素加的是d，不是加總和。
小結
線段樹讓每個節點代表一個區間，查詢和單點更新都是 (O(\log n))。懶標記把「整段加一個數」也變成 (O(\log n))，前提是這個運算對區間的影響可以延後再推。樹狀陣列用最低位 1 走前綴，程式更短，適合區間和。運算不可逆、或是區間修改，用線段樹。