POJ 3468 線段樹區間加減與區間求和：懶標記模板詳解

題目大意

序列長度 N ≤ 100,000，Q 次操作：
1. 區間加值：Add L R val
2. 區間求和：Query L R

線段樹 + 懶標記核心思想

• 每個節點維護：sum（區間和）、addv（懶標記，待下推的加值）
• 更新時：若當前區間完全包含在目標區間，直接打標記 addv += val，sum += val * 區間長度
• 查詢/遞歸前：下推標記到子節點，清空自身標記

關鍵代碼

const int MAXN = 100000;
ll sum[MAXN<<2], addv[MAXN<<2];

void push_up(int o) {
    sum[o] = sum[o<<1] + sum[o<<1|1];
}

void push_down(int o, int l, int r) {
    if (addv[o]) {
        int m = (l + r) >> 1;
        addv[o<<1] += addv[o];
        addv[o<<1|1] += addv[o];
        sum[o<<1] += (ll)(m - l + 1) * addv[o];
        sum[o<<1|1] += (ll)(r - m) * addv[o];
        addv[o] = 0;
    }
}

void update(int L, int R, int v, int l, int r, int o) {
    if (L <= l && r <= R) {
        addv[o] += v;
        sum[o] += (ll)v * (r - l + 1);
        return;
    }
    push_down(o, l, r);
    int m = (l + r) >> 1;
    if (L <= m) update(L, R, v, l, m, o<<1);
    if (m < R) update(L, R, v, m+1, r, o<<1|1);
    push_up(o);
}

ll query(int L, int R, int l, int r, int o) {
    if (L <= l && r <= R) return sum[o];
    push_down(o, l, r);
    int m = (l + r) >> 1;
    ll ans = 0;
    if (L <= m) ans += query(L, R, l, m, o<<1);
    if (m < R) ans += query(L, R, m+1, r, o<<1|1);
    push_up(o);
    return ans;
}

建樹

void build(int l, int r, int o) {
    addv[o] = 0;
    if (l == r) {
        scanf("%lld", &sum[o]);
        return;
    }
    int m = (l + r) >> 1;
    build(l, m, o<<1);
    build(m+1, r, o<<1|1);
    push_up(o);
}

複雜度

• 建樹：O(N)
• 單次更新/查詢：O(log N)
• 空間：O(4N)

模板適用場景

所有區間加法更新、區間求和查詢的問題，如 POJ 3468、HDU 1698、LOJ 1438 等。