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

問題描述

N (≤ 50,000) 個營地，初始各有若干士兵。M (≤ 40,000) 次操作：
Add i j：第 i 營地增加 j 人
Sub i j：第 i 營地減少 j 人
Query i j：詢問區間 [i, j] 總人數
End：本測試用例結束。
多測試用例，輸出格式 Case k:。

線段樹模板

維護區間和，支持單點增減、區間查詢。結構：

• sum[rt]：節點 rt 代表區間的和
• build(l, r, rt)：遞歸構建，葉子讀入初值
• update(p, add, l, r, rt)：單點 p 加 add（可為負）
• query(L, R, l, r, rt)：區間 [L, R] 求和

關鍵代碼

const int MAXN = 50000;
int sum[MAXN<<2];
void pushUp(int rt) { sum[rt] = sum[rt<<1] + sum[rt<<1|1]; }
void build(int l, int r, int rt) {
    if (l == r) { scanf("%d", &sum[rt]); return; }
    int m = (l+r)>>1;
    build(l, m, rt<<1);
    build(m+1, r, rt<<1|1);
    pushUp(rt);
}
void update(int p, int add, int l, int r, int rt) {
    if (l == r) { sum[rt] += add; return; }
    int m = (l+r)>>1;
    if (p <= m) update(p, add, l, m, rt<<1);
    else update(p, add, m+1, r, rt<<1|1);
    pushUp(rt);
}
int query(int L, int R, int l, int r, int rt) {
    if (L <= l && r <= R) return sum[rt];
    int m = (l+r)>>1, ret = 0;
    if (L <= m) ret += query(L, R, l, m, rt<<1);
    if (R > m) ret += query(L, R, m+1, r, rt<<1|1);
    return ret;
}

主程序

int main() {
    int T; scanf("%d", &T);
    for (int cas = 1; cas <= T; cas++) {
        int N; scanf("%d", &N);
        build(1, N, 1);
        printf("Case %d:\n", cas);
        char op[10];
        while (scanf("%s", op), op[0] != 'E') {
            int a, b; scanf("%d%d", &a, &b);
            if (op[0] == 'Q') printf("%d\n", query(a, b, 1, N, 1));
            else if (op[0] == 'S') update(a, -b, 1, N, 1);
            else update(a, b, 1, N, 1); // Add
        }
    }
    return 0;
}

複雜度

• 構建：O(N)
• 單次更新/查詢：O(log N)
• 總操作：O((N+M) log N)，N=5萬，M=4萬，極快

線段樹宏定義技巧

#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
// 調用時：build(lson); update(p, add, lson); query(L, R, lson);

簡化參數傳遞，代碼更精簡。

總結

HDU 1166 是線段樹入門經典題：單點更新、區間查詢、多測試用例。掌握標準模板（構建、pushUp、更新、查詢）即可輕鬆通過。注意輸入輸出格式、測試用例分隔、命令解析等工程細節。