POJ 3468：A Simple Problem with Integers（區間加、區間和，線段樹）

一、題目大意

維護一個長度為 N 的數組，支持兩種操作（Q 次）：
C a b c：區間 [a,b] 每個元素加 c
Q a b：查詢區間 [a,b] 的和

數據範圍：N, Q ≤ 100,000，數值大，需用 64 位整數。

二、解題思路：線段樹 + 惰性標記

線段樹節點存儲區間和 sum 和惰性標記 add（表示該區間整體待加的值）。
操作：
- 區間更新：若當前節點區間完全被覆蓋，直接更新 sum 和 add；否則下推標記，遞歸更新子節點，再上推 sum。
- 區間查詢：類似，完全覆蓋直接返回 sum，否則下推標記後遞歸查詢子節點。

三、代碼實現（C++）

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

#define ll long long
const int MAXN = 100010;

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

ll arr[MAXN];
int n, q;

void build(int l, int r, int idx) {
    tree[idx].l = l; tree[idx].r = r; tree[idx].add = 0;
    if (l == r) return;
    int mid = (l + r) >> 1;
    build(l, mid, idx << 1);
    build(mid + 1, r, idx << 1 | 1);
}

void pushDown(int idx) {
    if (tree[idx].add) {
        ll add = tree[idx].add;
        int lc = idx << 1, rc = idx << 1 | 1;
        tree[lc].sum += add * (tree[lc].r - tree[lc].l + 1);
        tree[rc].sum += add * (tree[rc].r - tree[rc].l + 1);
        tree[lc].add += add;
        tree[rc].add += add;
        tree[idx].add = 0;
    }
}

void update(int l, int r, ll val, int idx) {
    if (tree[idx].l > r || tree[idx].r < l) return;
    if (tree[idx].l >= l && tree[idx].r <= r) {
        tree[idx].sum += val * (tree[idx].r - tree[idx].l + 1);
        tree[idx].add += val;
        return;
    }
    pushDown(idx);
    update(l, r, val, idx << 1);
    update(l, r, val, idx << 1 | 1);
    tree[idx].sum = tree[idx << 1].sum + tree[idx << 1 | 1].sum;
}

ll query(int l, int r, int idx) {
    if (tree[idx].l > r || tree[idx].r < l) return 0;
    if (tree[idx].l >= l && tree[idx].r <= r) return tree[idx].sum;
    pushDown(idx);
    return query(l, r, idx << 1) + query(l, r, idx << 1 | 1);
}

int main() {
    while (scanf("%d%d", &n, &q) == 2) {
        for (int i = 1; i <= n; ++i) scanf("%lld", &arr[i]);
        build(1, n, 1);
        for (int i = 1; i <= n; ++i) update(i, i, arr[i], 1); // 初始化
        char op;
        int a, b; ll c;
        while (q--) {
            scanf(" %c", &op);
            if (op == 'C') {
                scanf("%d%d%lld", &a, &b, &c);
                update(a, b, c, 1);
            } else {
                scanf("%d%d", &a, &b);
                printf("%lld\n", query(a, b, 1));
            }
        }
    }
    return 0;
}

四、複雜度分析

• 建樹：O(N)
• 單次更新/查詢：O(log N)
• 總時間：O((N+Q) log N)
• 空間：O(N)

經典線段樹模板題，掌握惰性標記下推與上推是關鍵。