POJ 3468：區間加、區間和 (線段樹 Lazy Propagation)

問題描述

N, Q ≤ 100000。序列初始值 A_i。兩操作：
C a b c：區間 [a,b] 每元素加 c。
Q a b：查詢區間 [a,b] 和。
輸出所有查詢結果。和可能超 32 位，需 64 位整數。

線段樹 + 延遲標記

節點存儲：sum（區間和）、lazy（待下傳的加法標記）。

• PushDown：將 lazy 下傳給左右子節點，更新其 sum 和 lazy，清空自身 lazy。
• Update：區間完全覆蓋時直接更新 sum 和 lazy；否則 PushDown 遞歸左右，回溯 PushUp。
• Query：區間完全覆蓋返回 sum；否則 PushDown 遞歸查詢。

參考代碼 (C++)

#include 
using namespace std;
using ll = long long;
const int MAXN = 100005;
ll sum[MAXN<<2], lazy[MAXN<<2];

void pushUp(int rt) { sum[rt] = sum[rt<<1] + sum[rt<<1|1]; }
void pushDown(int rt, int l, int r) {
    if (lazy[rt]) {
        int mid = (l+r)>>1;
        sum[rt<<1] += lazy[rt] * (mid - l + 1);
        sum[rt<<1|1] += lazy[rt] * (r - mid);
        lazy[rt<<1] += lazy[rt];
        lazy[rt<<1|1] += lazy[rt];
        lazy[rt] = 0;
    }
}
void build(int rt, int l, int r) {
    lazy[rt] = 0;
    if (l == r) { cin >> sum[rt]; return; }
    int mid = (l+r)>>1;
    build(rt<<1, l, mid);
    build(rt<<1|1, mid+1, r);
    pushUp(rt);
}
void update(int rt, int l, int r, int L, int R, ll val) {
    if (L <= l && r <= R) {
        sum[rt] += val * (r - l + 1);
        lazy[rt] += val;
        return;
    }
    pushDown(rt, l, r);
    int mid = (l+r)>>1;
    if (L <= mid) update(rt<<1, l, mid, L, R, val);
    if (R > mid) update(rt<<1|1, mid+1, r, L, R, val);
    pushUp(rt);
}
ll query(int rt, int l, int r, int L, int R) {
    if (L <= l && r <= R) return sum[rt];
    pushDown(rt, l, r);
    int mid = (l+r)>>1;
    ll res = 0;
    if (L <= mid) res += query(rt<<1, l, mid, L, R);
    if (R > mid) res += query(rt<<1|1, mid+1, r, L, R);
    return res;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, Q;
    while (cin >> N >> Q) {
        build(1, 1, N);
        while (Q--) {
            char op; cin >> op;
            if (op == 'Q') {
                int a, b; cin >> a >> b;
                cout << query(1, 1, N, a, b) << '\n';
            } else {
                int a, b; ll c; cin >> a >> b >> c;
                update(1, 1, N, a, b, c);
            }
        }
    }
    return 0;
}

關鍵點

• 經典線段樹區間加、區間和模板，lazy 存儲「整個區間待加的值」。
• PushDown 時按子區間長度更新 sum。
• long long 必須，避免溢出。
• 輸入輸出量大，需 ios::sync_with_stdio(false); cin.tie(nullptr);。

複雜度

建樹 O(N)，單次操作 O(log N)，總 O((N+Q) log N)，10⁵ log 10⁵ 輕鬆通過。

總結

• 線段樹 Lazy Propagation 是區間修改、區間查詢的標準數據結構。
• 代碼模板化，熟練掌握 PushDown/PushUp 邏輯。
• 注意邊界：區間端點包含關係、遞歸終止條件。