線段樹 & BIT：區間查詢神器

問題場景

陣列 A = [5, 8, 6, 3, 2, 7, 2, 6]，給你大量查詢：

算 A[2..5] 的總和
算 A[0..7] 的最大值
把 A[3] 改成 10
再算 A[1..4] 的總和

如果直接掃陣列：每次查詢 O(n)、修改 O(1) → m 次查詢就是 O(mn)。

線段樹：建樹 O(n)，查詢/修改都 O(log n)。

線段樹結構

把陣列「分而治之」：根代表整段、左子代表左半、右子代表右半…直到葉節點 = 單個元素。

每個內部節點存「該區間的某種統計值」——可以是 sum, min, max, gcd…

操作

Build（O(n)）

遞迴從葉節點往上建。子節點建好後，父節點 = 兩子之和。

Query(l, r)（O(log n)）

要算 A[l..r] 的和，從根開始遞迴：

當前節點區間完全在 [l, r] 內 → 直接返回節點值
完全不重疊 → 返回 0
部分重疊 → 遞迴查左右子，相加

Update(i, value)（O(log n)）

從根往下找到 A[i] 的葉節點，修改值，一路往上更新祖先。

Pseudocode（區間和）

// tree 用陣列存（類似 heap）：node 的左子=2×node，右子=2×node+1

Algorithm Build(node, l, r):

if l == r: tree[node] ← A[l]; return

mid ← (l + r) / 2

Build(2×node, l, mid)

Build(2×node+1, mid+1, r)

tree[node] ← tree[2×node] + tree[2×node+1]

Algorithm Query(node, l, r, ql, qr):

if qr < l or ql > r: return 0 // 無重疊

if ql ≤ l and r ≤ qr: return tree[node] // 全包含

mid ← (l + r) / 2

return Query(2×node, l, mid, ql, qr) + Query(2×node+1, mid+1, r, ql, qr)

複雜度

操作	線段樹	暴力
Build	O(n)	—
Query	O(log n)	O(n)
Update（單點）	O(log n)	O(1)
空間	O(4n)	O(n)

m 次查詢 + u 次更新：

暴力：O(m × n + u)
線段樹：O(n + (m + u) × log n) — 大資料量贏太多。

BIT / Fenwick Tree：更省的選擇

如果你只要前綴和（A[0..i] 的和），有更簡單的工具：BIT (Binary Indexed Tree, 樹狀陣列)。

利用 lowbit 操作（i & -i 取最低位 1）跳躍式更新與查詢，code 短到能默寫：

Algorithm Update(i, delta):

while i ≤ n:

bit[i] ← bit[i] + delta

i ← i + (i & -i)

Algorithm Query(i): // 算 A[1..i] 前綴和

sum ← 0

while i > 0:

sum ← sum + bit[i]

i ← i - (i & -i)

return sum

BIT vs Segment Tree

	BIT	Segment Tree
程式碼長度	5-10 行	30+ 行
記憶體	O(n)	O(4n)
支援操作	前綴和、單點更新	更通用（min/max/gcd/區間更新）
速度（常數倍）	更快	略慢
易實作	簡單	較複雜

用對工具：只要前綴和 → BIT；要 min/max/gcd 或區間更新 → Segment Tree。

💡進階：區間更新 + 區間查詢

線段樹加上「延遲標記 (Lazy Propagation)」就能支援：

Update(l, r, value)：把 A[l..r] 都加 value
Query(l, r)：算 A[l..r] 和

兩個操作都 O(log n)。實作較複雜，期末考通常不會考，比賽 / 進階課才會。

📝考試會這樣考

題型一：給陣列，畫線段樹。 訣竅：對半切到剩一個，每個內部節點寫該區間的統計值。

題型二：跑一遍 Query 或 Update。 列出走訪了哪些節點，特別標出「完全包含」和「部分重疊」。

題型三：BIT 的 lowbit 怎麼運作？ 答：i & -i 取出 i 的最低位 1。例：12 = 1100₂，-12 = 0100₂（補碼），AND = 0100 = 4。所以 lowbit(12) = 4，BIT 中 bit[12] 管理 A[9..12] 共 4 格。

題型四：為什麼線段樹空間要 O(4n)？ 答：n 不是 2 的冪時，樹高 ⌈log n⌉ + 1，總節點數 ≤ 2 × 2^⌈log n⌉ - 1 ≤ 4n。

題型五：BIT 能查單區間 [l, r] 嗎？ 答：能。query(r) - query(l-1) 即可。

這章記住

線段樹：每節點存區間統計值，Query/Update O(log n)。
BIT：簡單版線段樹，只支援前綴和，但 code 短、記憶體小。
場景：頻繁區間查詢 + 偶爾更新。
進階：Lazy Propagation 支援區間更新（不在期末範圍內）。