HDU 1166 敵兵布陣：樹狀數組區間求和入門

問題描述

有 N 個敵兵營地，初始各有若干兵力。支援三種操作：

• Add i v：第 i 營地增加 v 兵力
• Sub i v：第 i 營地減少 v 兵力
• Query i j：查詢區間 [i, j] 總兵力

多測試案例，每案例以 End 結束。N ≤ 50,000，操作數未限但隱含 ≤ 50,000。

樹狀數組適用性

經典單點更新、區間查詢場景，樹狀數組（Binary Indexed Tree, BIT）完美契合：

• add(i, v)：O(log N)
• sum(i)（前綴和）：O(log N)
• 區間和 [l, r] = sum(r) - sum(l-1)

核心代碼

/* HDU 1166 敵兵布陣 - BIT */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 50000 + 5;
int c[MAXN], n;

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

void add(int i, int val) {
    for (; i <= n; i += lowbit(i)) c[i] += val;
}

int sum(int i) {
    int s = 0;
    for (; i > 0; i -= lowbit(i)) s += c[i];
    return s;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    for (int cas = 1; cas <= T; ++cas) {
        cin >> n;
        fill(c, c + n + 1, 0);
        for (int i = 1; i <= n; ++i) {
            int x; cin >> x; add(i, x);
        }
        cout << "Case " << cas << ":\n";
        string op;
        while (cin >> op) {
            if (op[0] == 'E') break; // End
            int x, y; cin >> x >> y;
            if (op[0] == 'A') add(x, y);
            else if (op[0] == 'S') add(x, -y);
            else if (op[0] == 'Q') cout << sum(y) - sum(x - 1) << "\n";
        }
    }
    return 0;
}

關鍵點

• 1-based 索引：樹狀數組標準用法，輸入營地編號直接用作下標。
• 初始化：逐個 add(i, x) 建樹，O(N log N)；也可用 O(N) 建樹優化，但 N=5e4 無壓力。
• 命令解析：用 op[0] 區分 'A'/'S'/'Q'/'E'，簡潔高效。
• 多案例隔離：每案例 fill(c, c+n+1, 0) 重置。

複雜度

• 建樹：O(N log N)
• 每操作：O(log N)
• 總體極快，記憶體 O(N)。

總結

HDU 1166 是樹狀數組教科書級入門題。它展示了 BIT 在「動態單點修改 + 區間和查詢」場景下的極致簡潔與高效。掌握 lowbit、add、sum 三個核心函數，即可輕鬆解決此類問題。建議初學者背誦模板，並理解「為什麼 i += lowbit(i) 能覆蓋所有包含 i 的區間」的直觀幾何意義。