POJ 3468 區間加與區間和：線段樹懶標記入門經典

問題描述

N 個整數（N≤10⁵），Q 次操作（Q≤10⁵）：

• C a b c：區間 [a,b] 每個元素加 c
• Q a b：查詢區間 [a,b] 和

數值範圍大，需 64 位整數。經典線段樹區間修改、區間查詢問題。

線段樹懶標記核心思想

區間加操作不下推到葉子，而是打標記 add[rt] 記錄「該節點整體待加值」。查詢或進一步修改時再 pushdown 將標記傳給子節點。

關鍵操作

// 上傳：用子節點信息更新父節點
void pushup(int rt) {
    sum[rt] = sum[rt<<1] + sum[rt<<1|1];
}

// 下推：將懶標記傳給子節點，並更新子節點 sum
void pushdown(int l, int r, int rt) {
    if (add[rt] != 0) {
        int mid = (l + r) >> 1;
        // 左子節點
        add[rt<<1] += add[rt];
        sum[rt<<1] += add[rt] * (mid - l + 1);
        // 右子節點
        add[rt<<1|1] += add[rt];
        sum[rt<<1|1] += add[rt] * (r - mid);
        // 清空當前標記
        add[rt] = 0;
    }
}

完整實現

#include 
using namespace std;
using ll = long long;
const int MAXN = 100005;

ll sum[MAXN<<2], add[MAXN<<2];
int a[MAXN];

void build(int l, int r, int rt) {
    add[rt] = 0;
    if (l == r) { sum[rt] = a[l]; return; }
    int mid = (l+r)>>1;
    build(l, mid, rt<<1);
    build(mid+1, r, rt<<1|1);
    pushup(rt);
}

void update(int L, int R, ll val, int l, int r, int rt) {
    if (L <= l && r <= R) {
        add[rt] += val;
        sum[rt] += val * (r - l + 1);
        return;
    }
    pushdown(l, r, rt);
    int mid = (l+r)>>1;
    if (L <= mid) update(L, R, val, l, mid, rt<<1);
    if (R > mid) update(L, R, val, mid+1, r, rt<<1|1);
    pushup(rt);
}

ll query(int L, int R, int l, int r, int rt) {
    if (L <= l && r <= R) return sum[rt];
    pushdown(l, r, rt);
    int mid = (l+r)>>1;
    ll res = 0;
    if (L <= mid) res += query(L, R, l, mid, rt<<1);
    if (R > mid) res += query(L, R, mid+1, r, rt<<1|1);
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    while (cin >> n >> q) {
        for (int i = 1; i <= n; ++i) cin >> a[i];
        build(1, n, 1);
        while (q--) {
            char op; cin >> op;
            if (op == 'C') {
                int a, b; ll c; cin >> a >> b >> c;
                update(a, b, c, 1, n, 1);
            } else {
                int a, b; cin >> a >> b;
                cout << query(a, b, 1, n, 1) << '\n';
            }
        }
    }
    return 0;
}

關鍵點總結

常見錯誤

• 忘記 pushdown 導致子節點 sum 過期
• pushdown 中子節點長度計算錯誤（左長 mid-l+1，右長 r-mid）
• 未用 long long 導致溢出（和可達 10⁵ × 10⁹ = 10¹⁴）
• 遞歸參數順序混淆

複雜度

• 構建：O(N)
• 單次修改/查詢：O(log N)
• 總計：O((N+Q) log N)，完全滿足限制