把陣列建成一棵「區間樹」,區間查詢、區間更新全都 O(log n)。懶標記是它的殺手鐧。
O(log n)。而懶標記(lazy propagation)更狠:連「把一整段區間全部加值」也能 O(log n) —— 訣竅是碰到「整段都被蓋住」的節點時,不急著一片片改葉子,先在節點上記個「欠著」的標記,等真的要用到下面才把它推下去。跟樹狀陣列(Fenwick)比,線段樹更萬用、還能直接做區間更新。
每個節點管一段區間 —— 根管整個 [0, n-1],往下對半切成左右,葉子管單一元素。節點存那段的和(換個合併運算就能存 min / max / gcd)。
區間查詢 O(log n) —— 要查的區間會被拆成 O(log n) 個「剛好對齊」的節點,把它們的值合併起來。不用一格一格加。
單點更新 O(log n) —— 改一個元素:更新對應葉子,再一路往上把祖先的和修正。
比 Fenwick 萬用 —— 樹狀陣列基本款只做「單點更新 + 前綴和」;線段樹能做區間更新,也能算 min / max / gcd 這類「不可逆」的查詢。
問題 —— 「把 [l,r] 每個元素都 +x」,如果逐葉更新,一次就 O(區間長),慢。
解法:整段被蓋住就打標記 —— 遞迴時碰到「整段都在更新範圍內」的節點,不往下改葉子,只在這節點記一個 lazy 標記,並直接把它的和加好(和 += x × 區間長)。
push down:要用到才推下去 —— 之後有查詢或更新要穿過這個節點、往下走,進去前才把 lazy 推給兩個孩子(孩子的和、孩子的 lazy 一起更新),然後清掉自己的標記。
於是區間更新也 O(log n) —— 「欠著、用到才算」,所以叫「懶」。標記像一張貼在部門的便利貼,誰真的要查才發下去。
O(log n) 個對齊節點合併。log 級。每個主管節點記「我這條線下面共幾人」。問某部門總人數,問到那個節點就好,不用一個個數。
「這整個部門每人加薪 3000」先在部門掛張便利貼(懶標記),誰真的要查自己薪水,才把便利貼發下去 —— 這就是 push down。
快速問「這段時間的總和 / 最大值」,還能一次把某段時間整批調整。
對陣列 [2,5,1,4] 的線段樹,做「[1,3] 每個元素 +3」。節點小框上面是它管的區間、裡面是和。看它怎麼在 [2,3] 打懶標記(琥珀 +3)就收工、葉子完全不動,之後一次查詢才把標記推下去。紫框是正在走的、綠框是算好的。按「下一步」。
從建樹 + 區間和、單點更新,到懶標記區間加(核心)、push down 拆解、區間最小值、區間賦值、陣列式實作,再到建樹 O(n)、對照 Fenwick、小結。
❌ 忘了 push down —— 查詢 / 更新要穿過帶 lazy 的節點,卻沒先把標記推下去 → 讀到過時的值。往下走之前一定先 push down。
❌ lazy 合併規則寫錯 —— 「加值」型可以累加(lazy += x);但「賦值 assign」型不一樣(後蓋前,用 None 當「沒標記」),合併規則要分清楚。
❌ 陣列開太小 —— 遞迴式線段樹習慣開 4n;開 2n 在 n 非 2 次方時可能越界。
❌ 殺雞用牛刀 —— 只要「單點更新 + 前綴和」,樹狀陣列(Fenwick)更短更快,不必動用線段樹。
把答案打到對話裡,我幫你對。