POJ 3468 線段樹區間增減與區間求和詳解

題目大意

給定 n 個數，支援兩種操作：

• C A B C：區間 [A, B] 內每個數增加 C
• Q A B：查詢區間 [A, B] 的和

經典的線段樹「區間更新、區間查詢」問題，需使用 Lazy Propagation（懶標記）技術。

核心思路：懶標記機制

線段樹每個節點維護兩個關鍵值：

• sum：該區間所有元素的和
• add：該區間的「公共增量」（懶標記），表示該區間所有元素尚未下推給子節點的待增加值

向上更新（Pull）

當子節點的 sum 發生變化後，父節點的 sum 需重新計算：tree[v].sum = tree[v*2].sum + tree[v*2+1].sum。

向下更新

當需要訪問子節點時，必須先將當前節點的 add 下推給左右子節點：

tree[v*2].add += tree[v].add;
tree[v*2+1].add += tree[v].add;
tree[v*2].sum += tree[v].add * (tree[v*2].r - tree[v*2].l + 1);
tree[v*2+1].sum += tree[v].add * (tree[v*2+1].r - tree[v*2+1].l + 1);
tree[v].add = 0;

關鍵同步原則：add 的變化與 sum 的變化必須同步，否則查詢結果會出錯。

完整程式碼

#include <stdio.h>
#include <string.h>
#define LL long long
const int maxn = 100005;
__int64 a[maxn];

struct Node {
    int l, r;
    LL sum, add;
} tree[maxn << 2];

void build(int v, int l, int r) {
    tree[v].l = l; tree[v].r = r; tree[v].add = 0;
    if (l == r) { tree[v].sum = a[r]; return; }
    int mid = (l + r) >> 1;
    build(v*2, l, mid);
    build(v*2+1, mid+1, r);
    tree[v].sum = tree[v*2].sum + tree[v*2+1].sum;
}

void update(int v, int l, int r, __int64 add) {
    tree[v].sum += (r - l + 1) * add; // 當前區間 sum 必須更新
    if (tree[v].l == l && tree[v].r == r) { // 完全覆蓋
        tree[v].add += add; return;
    }
    int mid = (tree[v].l + tree[v].r) >> 1;
    // 下推懶標記
    if (tree[v].add) {
        tree[v*2].add += tree[v].add;
        tree[v*2+1].add += tree[v].add;
        tree[v*2].sum += tree[v].add * (tree[v*2].r - tree[v*2].l + 1);
        tree[v*2+1].sum += tree[v].add * (tree[v*2+1].r - tree[v*2+1].l + 1);
        tree[v].add = 0;
    }
    if (r <= mid) update(v*2, l, r, add);
    else if (l > mid) update(v*2+1, l, r, add);
    else {
        update(v*2, l, mid, add);
        update(v*2+1, mid+1, r, add);
    }
}

__int64 query(int v, int l, int r) {
    if (tree[v].l == l && tree[v].r == r) return tree[v].sum;
    int mid = (tree[v].l + tree[v].r) >> 1;
    // 下推懶標記
    if (tree[v].add) {
        tree[v*2].add += tree[v].add;
        tree[v*2+1].add += tree[v].add;
        tree[v*2].sum += tree[v].add * (tree[v*2].r - tree[v*2].l + 1);
        tree[v*2+1].sum += tree[v].add * (tree[v*2+1].r - tree[v*2+1].l + 1);
        tree[v].add = 0;
    }
    if (r <= mid) return query(v*2, l, r);
    else if (l > mid) return query(v*2+1, l, r);
    else return query(v*2, l, mid) + query(v*2+1, mid+1, r);
}

int main() {
    int n, m; char ch[2]; int l, r; __int64 ans, add;
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%I64d", &a[i]);
    build(1, 1, n);
    while (m--) {
        scanf("%s", ch);
        if (ch[0] == 'C') {
            scanf("%d %d %I64d", &l, &r, &add);
            update(1, l, r, add);
        } else {
            scanf("%d %d", &l, &r);
            ans = query(1, l, r);
            printf("%I64d\n", ans);
        }
    }
    return 0;
}

調試心得

我被書上誤導了，導致調試了一下午…… 所以，還是要相信自己的想法，不要完全依賴別人的。

• 區間更新時：無論當前節點是否被完全覆蓋，其 sum 都要先加上 (r-l+1)*add，因為查詢時可能直接用到該節點的 sum。
• 懶標記下推時機：只有在「需要訪問子節點」且「當前節點有懶標記」時才下推。
• 完全覆蓋判斷：tree[v].l == l && tree[v].r == r 表示當前節點區間完全被更新區間覆蓋，此時只需更新 add 和 sum，無需遞歸子節點。

總結

線段樹懶標記的核心在於「延遲更新」與「同步維護」。理解透 add（增量標記）與 sum（區間和）的同步關係，是寫對區間更新題目的關鍵。