題幹與適用場景
給定長度為 n 的整數陣列，線上處理兩種操作：將閉區間 [l, r] 每個元素加上 delta，查詢 [l, r] 總和。要求初始化 O(n)，每次更新與查詢 O(log n)，允許 O(n) 額外空間。先確認索引為閉區間、delta 可為負數，以及是否需要持久化版本。
面試官考察點
強回答先寫節點不變量：tree[p] 永遠是節點覆蓋區間的真實總和，lazy[p] 表示尚未寫入子節點、但已計入 tree[p] 的統一增量。要能解釋完整覆蓋只更新目前節點、部分覆蓋先 push 再遞迴，並將增量乘上區間長度。
回答前需要釐清的問題
- 更新是加法、賦值還是取最大值？不同操作的 lazy 合併律不同，不能套用同一標記。
- 查詢是總和、最小值還是最大值？節點聚合與標記公式會改變。
- 區間是否閉合？下文採閉區間
[l, r]；半開區間需統一分割與長度。 - 數值範圍多大？
tree[p] + delta * length可能溢出 32 位整數，應選足夠寬的型別。
推薦解法與推導
用陣列儲存隱式二元樹。節點 [lo, hi] 的中點為 mid，左右子區間為 [lo, mid] 與 [mid+1, hi]。完整覆蓋更新時，把 delta * (hi-lo+1) 加到 tree[p]，並將 delta 累積到 lazy[p]；子節點真值暫不修改。
class LazySumTree:
def __init__(self, values):
self.n = len(values)
self.tree = [0] * (4 * max(1, self.n))
self.lazy = [0] * len(self.tree)
if self.n:
self._build(1, 0, self.n - 1, values)
def _apply(self, p, lo, hi, delta):
self.tree[p] += delta * (hi - lo + 1)
self.lazy[p] += delta
def _push(self, p, lo, hi):
if self.lazy[p] == 0 or lo == hi:
return
mid = (lo + hi) // 2
d = self.lazy[p]
self._apply(p * 2, lo, mid, d)
self._apply(p * 2 + 1, mid + 1, hi, d)
self.lazy[p] = 0完整實作還需遞迴 add 與 total，遵循同一不變量：完整覆蓋呼叫 _apply；部分覆蓋先 _push，子呼叫返回後重算父節點。每層只訪問常數個邊界節點，因此更新與查詢皆為 O(log n)，樹與標記陣列使用 O(n) 空間。
替代方案與取捨
只有單點更新與前綴和時，Fenwick 樹程式較短、常數較小；只有離線區間加法且最後一次讀取時，差分陣列更簡單。懶標記線段樹適合線上、區間更新與區間聚合同時存在，但實作複雜度較高。若更新是區間賦值，需要額外的「是否有賦值標記」並定義賦值覆蓋舊加法的順序。
失敗場景、邊界與反例
- 忘記乘區間長度，
[2, 5]加 3 只增加 3 而不是 12。 - 完整覆蓋後仍遞迴子節點，失去 lazy 效益且可能重複套用增量。
- push 後不清零，下一次存取會重複加同一標記。
- 部分更新後不重算父節點，後續完整覆蓋查詢會回傳舊總和。
- 混用閉區間與半開區間，導致單元素或
mid+1越界；入口應統一檢查空陣列、l > r和n=0。
測試與驗證清單
用樸素陣列作 oracle，隨機產生更新與查詢並逐步比較；覆蓋單元素、全陣列、左右邊界、負增量、重複覆蓋與全相同值。另斷言每次遞迴返回後父節點等於兩個子節點總和，並在大陣列檢查整數型別不溢位。迭代版則增加跨層 push 等價性測試。
追問與延伸
如何同時支援區間賦值與區間加法？
每個節點維護可選賦值標記與加法標記。新賦值覆蓋舊賦值與舊加法；新加法累積在已有賦值之後。push 時先下發賦值，再下發加法，順序是正確性的核心。
如何支援區間最小值？
將 tree[p] 改為區間最小值；區間加法對最小值只需加 delta，lazy 仍可累積。若加入區間取最小或取最大，標記不再只是加法，需要 segment tree beats 等更複雜不變量。
如何取得歷史版本？
採用持久化線段樹，對更新路徑複製節點並共用未修改子樹；每次更新約複製 O(log n) 個節點，根指標代表一個版本，空間隨更新次數成長。