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

問題描述

N 個營地（N ≤ 50,000），初始人數給定。M ≤ 40,000 操作：

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

線段樹模板

• 節點存儲區間和 sum
• 建樹 O(N)，遞歸構建左右子樹
• 單點更新 O(log N)：遞歸找到葉子修改，回溯更新祖先
• 區間查詢 O(log N)：區間完全包含直接返回，否則拆分左右子區間

參考代碼（C++）

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

const int MAXN = 50005;
int a[MAXN];
struct Node { int l, r, sum; } tree[MAXN << 2];

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

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

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

int main() {
    int T; scanf("%d", &T);
    for (int cas = 1; cas <= T; cas++) {
        int N; scanf("%d", &N);
        for (int i = 1; i <= N; i++) scanf("%d", &a[i]);
        build(1, N, 1);
        printf("Case %d:\n", cas);
        char cmd[10];
        while (scanf("%s", cmd)) {
            if (cmd[0] == 'E') break;
            int x, y; scanf("%d%d", &x, &y);
            if (cmd[0] == 'Q') printf("%d\n", query(1, x, y));
            else if (cmd[0] == 'A') update(1, x, y);
            else update(1, x, -y); // Sub
        }
    }
    return 0;
}

複雜度分析

• 建樹：O(N)
• 每操作：O(log N)
• 總時間：O((N + M) log N)，完全滿足限制
• 空間：O(N)

關鍵點

1. 線段樹是區間查詢 + 單點更新的標準數據結構
2. 注意 Add/Sub 只是單點加減，非區間操作
3. 輸入量大，建議用 scanf/printf