如何實作支援區間加法與區間求和的懶標記線段樹？

題幹與適用場景

給定長度為 n 的整數陣列，線上處理兩種操作：將閉區間 [l, r] 每個元素加上 delta，查詢 [l, r] 總和。要求初始化 O(n)，每次更新與查詢 O(log n)，允許 O(n) 額外空間。先確認索引為閉區間、delta 可為負數，以及是否需要持久化版本。

面試官考察點

強回答先寫節點不變量：tree[p] 永遠是節點覆蓋區間的真實總和，lazy[p] 表示尚未寫入子節點、但已計入 tree[p] 的統一增量。要能解釋完整覆蓋只更新目前節點、部分覆蓋先 push 再遞迴，並將增量乘上區間長度。

回答前需要釐清的問題

1. 更新是加法、賦值還是取最大值？不同操作的 lazy 合併律不同，不能套用同一標記。
2. 查詢是總和、最小值還是最大值？節點聚合與標記公式會改變。
3. 區間是否閉合？下文採閉區間 [l, r]；半開區間需統一分割與長度。
4. 數值範圍多大？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) 個節點，根指標代表一個版本，空間隨更新次數成長。