HDU 1166 敵兵佈陣：樹狀數組 (BIT) 單點修改區間查詢

HDU 1166 敵兵佈陣：樹狀數組經典應用

題目大意

N ≤ 50000 營地，初始人數。最多 40000 操作：
Add i j：第 i 營地 +j
Sub i j：第 i 營地 -j
Query i j：區間 [i,j] 總和
End：結束本測資

資料結構：Binary Indexed Tree (Fenwick Tree)

• sum(i)：前 i 項和，O(log N)。
• add(i, delta)：單點加 delta，O(log N)。
• 區間和 [l,r] = sum(r) - sum(l-1)。

核心程式碼（C）

#include <stdio.h>
#include <string.h>
#define MAX 50010

int bit[MAX], n;

int lowbit(int x) { return x & -x; }

void add(int i, int delta) {
    while (i <= MAX) { bit[i] += delta; i += lowbit(i); }
}

int query(int i) {
    int s = 0;
    while (i > 0) { s += bit[i]; i -= lowbit(i); }
    return s;
}

int main() {
    int T, kase = 1;
    scanf("%d", &T);
    while (T--) {
        memset(bit, 0, sizeof(bit));
        scanf("%d", &n);
        for (int i=1;i<=n;i++) {
            int v; scanf("%d", &v);
            add(i, v);
        }
        printf("Case %d:\n", kase++);
        char op[10];
        while (scanf("%s", op), strcmp(op, "End")) {
            int x, y; scanf("%d%d", &x, &y);
            if (op[0]=='Q') printf("%d\n", query(y)-query(x-1));
            else if (op[0]=='A') add(x, y);
            else if (op[0]=='S') add(x, -y);
        }
    }
    return 0;
}

複雜度

• 建樹：O(N log N)。
• 單次操作：O(log N)。
• 總時間遠小於 1 秒。