HDU 1166 敵兵布陣：線段樹實現區間求和與單點更新

問題描述

有 N（≤ 50,000）個營地排成一線，每個營地初始人數已知。需處理最多 40,000 條指令：

• Add i j：第 i 個營地增加 j 人。
• Sub i j：第 i 個營地減少 j 人。
• Query i j：詢問區間 [i, j] 總人數。
• End：結束當前測試案例。

輸出格式為 Case k: 後跟每個 Query 的答案。

資料結構選擇：線段樹

線段樹能在 O(log N) 完成單點修改與區間求和，完美契合本題時限。每個節點存儲區間和 sum，葉子節點對應單個營地人數。

核心操作

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

void update(int pos, int val, int idx) {
    tr[idx].sum += val;
    if (tr[idx].l == tr[idx].r) return;
    int mid = (tr[idx].l + tr[idx].r) >> 1;
    if (pos <= mid) update(pos, val, idx << 1);
    else update(pos, val, idx << 1 | 1);
}

int query(int L, int R, int idx) {
    if (L <= tr[idx].l && tr[idx].r <= R) return tr[idx].sum;
    int mid = (tr[idx].l + tr[idx].r) >> 1, ans = 0;
    if (L <= mid) ans += query(L, R, idx << 1);
    if (R > mid) ans += query(L, R, idx << 1 | 1);
    return ans;
}

完整代碼（C++）

#include <cstdio>
#include <cstring>
const int MAXN = 50000;
struct Node { int l, r, sum; } tr[MAXN << 2];
int a[MAXN + 5];

void build(int l, int r, int idx) {
    tr[idx].l = l; tr[idx].r = r;
    if (l == r) { tr[idx].sum = a[l]; return; }
    int mid = (l + r) >> 1;
    build(l, mid, idx << 1);
    build(mid + 1, r, idx << 1 | 1);
    tr[idx].sum = tr[idx << 1].sum + tr[idx << 1 | 1].sum;
}
void update(int pos, int val, int idx) {
    tr[idx].sum += val;
    if (tr[idx].l == tr[idx].r) return;
    int mid = (tr[idx].l + tr[idx].r) >> 1;
    if (pos <= mid) update(pos, val, idx << 1);
    else update(pos, val, idx << 1 | 1);
}
int query(int L, int R, int idx) {
    if (L <= tr[idx].l && tr[idx].r <= R) return tr[idx].sum;
    int mid = (tr[idx].l + tr[idx].r) >> 1, ans = 0;
    if (L <= mid) ans += query(L, R, idx << 1);
    if (R > mid) ans += query(L, R, idx << 1 | 1);
    return ans;
}
int main() {
    int T, n, kase = 0; scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
        build(1, n, 1);
        printf("Case %d:\n", ++kase);
        char op[10];
        while (scanf("%s", op) && op[0] != 'E') {
            int x, y; scanf("%d%d", &x, &y);
            if (op[0] == 'A') update(x, y, 1);
            else if (op[0] == 'S') update(x, -y, 1);
            else printf("%d\n", query(x, y, 1));
        }
    }
    return 0;
}

複雜度與技巧

• 建樹 O(N)，單次操作 O(log N)，總時間 O((N+Q) log N)。
• 輸入用 scanf，輸出用 printf，避免 iostream 慢速。
• 數組開 4×N 保證線段樹節點足夠。