線段樹區間更新與懶惰標記詳解：NEFU 1111 題目實戰

線段樹區間更新與懶惰標記詳解：NEFU 1111 題目實戰

題目核心

維護一個數列，支援兩種操作：

1. 區間加法：add(d, L, R) 將區間 [L,R] 每個元素加 d。
2. 區間最小值查詢：query(L, R) 返回區間最小值。

數據範圍大，需 O(log n) 處理，引入 懶惰標記 延遲下傳。

懶惰標記機制

• tree[node]：該區間當前最小值（已包含本節點標記）。
• lazy[node]：待向子節點傳遞的增量。
• pushdown(node)：將 lazy[node] 下推給左右子節點，更新其 tree 與 lazy，自身 lazy 歸零。

關鍵代碼片段

#define MAXN 1000010
long long tree[MAXN<<2], lazy[MAXN<<2];

void build(int l, int r, int node) {
    if (l == r) { scanf("%lld", &tree[node]); return; }
    int mid = (l+r)>>1;
    build(l, mid, node<<1);
    build(mid+1, r, node<<1|1);
    tree[node] = min(tree[node<<1], tree[node<<1|1]);
}

void pushdown(int node) {
    if (lazy[node]) {
        lazy[node<<1]   += lazy[node];
        lazy[node<<1|1] += lazy[node];
        tree[node<<1]   += lazy[node];
        tree[node<<1|1] += lazy[node];
        lazy[node] = 0;
    }
}

void update(int L, int R, long long val, int l, int r, int node) {
    if (L <= l && r <= R) {
        tree[node] += val;
        lazy[node] += val;
        return;
    }
    pushdown(node);
    int mid = (l+r)>>1;
    if (L <= mid) update(L, R, val, l, mid, node<<1);
    if (R > mid)  update(L, R, val, mid+1, r, node<<1|1);
    tree[node] = min(tree[node<<1], tree[node<<1|1]);
}

long long query(int L, int R, int l, int r, int node) {
    if (L <= l && r <= R) return tree[node];
    pushdown(node);
    int mid = (l+r)>>1;
    long long ans = 9e18;
    if (L <= mid) ans = min(ans, query(L, R, l, mid, node<<1));
    if (R > mid)  ans = min(ans, query(L, R, mid+1, r, node<<1|1));
    return ans;
}

環形區間處理技巧

題目中區間可能跨越邊界（如 L > R），拆分為兩段：
[L, n] 和 [1, R]，分別操作後取最小值。

複雜度與空間

• 建樹：O(n)
• 單次更新/查詢：O(log n)
• 空間：4 * n 足夠（開 MAXN<<2）

避坑指南

1. pushdown 必須在 遞歸進入子節點前 執行，否則子節點數值不準。
2. lazy 累加而非覆蓋：多次區間加法疊加。
3. 查詢時同樣要 pushdown，保證訪問到的節點數值是最新的。
4. 邊界條件：l==r 為葉子，不再遞歸。

舉一反三

同框架可擴展支援：區間賦值（標記覆蓋）、區間乘法、區間最大值/求和、歷史最值等。核心在於設計合適的 lazy 語義與 pushdown/pushup 邏輯。