如果你需要反覆查詢「第 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)：遞迴建，葉節點放原始值，內部節點放子節點的合併結果。
區間查詢 O(log n)：
int query(int node, int start, int end, int L, int R) {
if (R < start || L > end) return 0; // 完全不重疊
if (L <= start && end <= R) return tree[node]; // 完全包含
// 部分重疊 → 拆成兩邊
int mid = (start + end) / 2;
return query(left, start, mid, L, R) +
query(right, mid+1, end, L, R);
}三種情況：完全不重疊就跳過、完全包含就直接回傳、部分重疊就拆。
單點更新 O(log n)：修改葉節點的值，沿路更新所有包含這個點的祖先節點。
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(left, start, mid, L, R, val);
updateRange(right, mid+1, end, L, R, val);
tree[node] = tree[left] + tree[right];
}有了 Lazy Propagation，區間更新從 O(n log n) 降到 O(log n)。
什麼時候不需要線段樹？
- 只需要前綴和、不需要最值 → Fenwick Tree（程式碼短三倍）
- 資料不會改變 → 前綴和陣列就好
- 單次查詢 → 暴力加總就好，建樹的 overhead 不值得
線段樹是重型武器——殺雞不用牛刀，但面對十萬次區間查詢混合十萬次更新，它是正解。
線段樹大概是「實作難度最高但概念最直覺」的資料結構——把區間切一半、再切一半，直到切到單一元素。分治法的暴力美學。