POJ 3468 區間加/區間和：線段樹懶標記模板

題目大意

• 序列長度 N ≤ 100,000，初始值 ±1e9。
• Q ≤ 100,000 操作：
   `C a b c`：區間 [a,b] 每個元素加 c（|c|≤10000）。
   `Q a b`：查詢區間 [a,b] 和。
• 答案可能超 32 位，需 64 位整數。

線段樹懶標記

• 節點存 `sum`（區間和）、`lazy`（待下推的加法標記）。
• `pushDown`：將 `lazy` 分配給左右子節點，更新子節點 `sum` 並累加子節點 `lazy`。
• 區間更新：完全覆蓋時直接加標記，否則下推後遞歸。
• 區間查詢：完全覆蓋返回 `sum`，否則下推後遞歸合併。

完整代碼

#include 
using namespace std;
using ll = long long;
const int MAXN = 100000;
ll sum[MAXN*4], lazy[MAXN*4];
int n, q;

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

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

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

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

int main() {
    scanf("%d%d", &n, &q);
    build(1, 1, n);
    while (q--) {
        char op; scanf(" %c", &op);
        if (op == 'C') {
            int a, b; ll c; scanf("%d%d%lld", &a, &b, &c);
            update(1, 1, n, a, b, c);
        } else {
            int a, b; scanf("%d%d", &a, &b);
            printf("%lld\n", query(1, 1, n, a, b));
        }
    }
    return 0;
}

複雜度

• 構建 O(N)。
• 單次更新/查詢 O(log N)。
• 總 O((N+Q) log N)，記憶體 O(N)。