如果你需要反覆查詢「第 L 到第 R 個的總和/最大值/最小值」，同時還會修改資料，線段樹就是為這個場景而生的。
區間查詢和更新都要快
線段樹把區間查詢和更新都做到 O(log n)，暴力法是 O(n)。代價是 O(4n) 的額外空間和較高的實作複雜度。如果你只需要前綴和且不需要區間最值，Fenwick Tree 更簡潔。
它解決什麼問題？
想像你有一個十萬筆的陣列，需要反覆回答「第 3000 到第 7000 筆的總和是多少？」然後有人改了第 5000 筆的值，再問一次。
暴力法每次加總都要 O(n)。前綴和可以 O(1) 查詢，但修改之後要 O(n) 重建。線段樹讓兩者都是 O(log n)。
結構：每個節點管一段區間
陣列: [1, 3, 5, 7, 9, 11]
[0,5]=36
/ \
[0,2]=9 [3,5]=27
/ \ / \
[0,1]=4 [2]=5 [3,4]=16 [5]=11
/ \ / \
[0]=1 [1]=3 [3]=7 [4]=9每個節點存一段區間的預計算結果（這裡是和）。查詢 [1,4] 時，不用加五個數字——只需要取 [1] + [2] + [3,4] = 3 + 5 + 16 = 24，三個節點搞定。
三個核心操作
建樹 O(n)：遞迴建，葉節點放原始值，內部節點放子節點的合併結果。
void build(int node, int start, int end) {
if (start == end) {
tree[node] = arr[start]; // 葉節點放原始值
} else {
int mid = (start + end) / 2;
build(2*node, start, mid); // 左子節點
build(2*node+1, mid+1, end); // 右子節點
tree[node] = tree[2*node] + tree[2*node+1]; // 內部節點 = 合併子節點
}
}tree[node] = 左 + 右 這行是整棵樹的靈魂——把這裡的 + 換成 min、max、gcd，同一套 code 就變成區間最小、最大、最大公因數查詢，樹的骨架完全不用動。
區間查詢 O(log n)：
int query(int node, int start, int end, int L, int R) {
if (R < start || L > end) return 0; // 完全不重疊（預設值：和用 0，min/max 要改 ±∞，見下表）
if (L <= start && end <= R) return tree[node]; // 完全包含
// 部分重疊 → 拆成兩邊
int mid = (start + end) / 2;
return query(2*node, start, mid, L, R) +
query(2*node+1, mid+1, end, L, R);
}三種情況：完全不重疊就跳過、完全包含就直接回傳、部分重疊就拆。
單點更新 O(log n)：修改葉節點的值，沿路更新所有包含這個點的祖先節點。
延續剛剛那句「換掉合併運算就換掉整個用途」，常見的可換運算長這樣——每種都要配一個對的預設值（查詢不重疊區間時回傳它，才不會污染結果）：
| 查詢類型 | 合併方式 | 不重疊時的預設值 |
|---|---|---|
| 區間和 | a + b | 0 |
| 區間最小值 | min(a, b) | +∞ |
| 區間最大值 | max(a, b) | -∞ |
| 區間 GCD | gcd(a, b) | 0 |
| 區間乘積 | a × b | 1 |
預設值選錯是實務上最陰的 bug——區間最小值若把預設寫成 0，資料全是正數時永遠回傳 0，錯得無聲無息。
Lazy Propagation：區間更新的救星
如果要「把 [0, 100000] 每個元素都 +5」，一個一個更新就完蛋了。
Lazy Propagation 的想法：先打個標記「這整段 +5」，等到有人真的來查這段的子區間時再往下推。
void updateRange(int node, int start, int end, int L, int R, int val) {
if (lazy[node] != 0) pushDown(node); // 有標記先下推
if (R < start || L > end) return;
if (L <= start && end <= R) {
tree[node] += (end - start + 1) * val;
lazy[node] += val; // 打懶標記，不往下走
return;
}
// 部分重疊才遞迴
int mid = (start + end) / 2;
updateRange(2*node, start, mid, L, R, val);
updateRange(2*node+1, mid+1, end, L, R, val);
tree[node] = tree[2*node] + tree[2*node+1];
}有了 Lazy Propagation，區間更新從 O(n log n) 降到 O(log n)。
什麼時候不需要線段樹？
- 只需要前綴和、不需要最值 → Fenwick Tree（程式碼短三倍）
- 資料不會改變 → 前綴和陣列就好
- 單次查詢 → 暴力加總就好，建樹的 overhead 不值得
線段樹是重型武器——殺雞不用牛刀，但面對十萬次區間查詢混合十萬次更新，它是正解。
🎬 互動視覺化：區間查詢結構對照 — 拉一段 [L, R]，看線段樹怎麼只點亮 O(log n) 個節點就湊出整段答案，而不是把區間裡每個元素都掃一遍。
線段樹大概是「實作難度最高但概念最直覺」的資料結構——把區間切一半、再切一半，直到切到單一元素。分治法的暴力美學。
接下來往哪走
- Fenwick Tree (BIT) 樹狀陣列 — 只要前綴和的話，程式碼短三倍的替代方案
- Prefix Sum 前綴和 & Difference Array 差分陣列 — 資料不變時的輕量前身，線段樹是它「可修改」的升級版
- 持久化線段樹：舊版本不用整棵複製，只複製一條路徑 — 線段樹的進階：讓每次修改都保留歷史版本