HDU 1166 敵兵布陣：樹狀數組（Binary Indexed Tree）實現

樹狀數組核心操作

lowbit(x) = x & (-x) 取最低位 1。
update(i, delta)：向上更新所有包含 i 的區間。
query(i)：向下累加前綴和。
區間和 query(r) - query(l-1)。

完整代碼

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 50005;
int bit[MAXN], n;
int lowbit(int x) { return x & -x; }
void add(int idx, int val) {
    for (; idx <= n; idx += lowbit(idx)) bit[idx] += val;
}
int sum(int idx) {
    int res = 0;
    for (; idx > 0; idx -= lowbit(idx)) res += bit[idx];
    return res;
}
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int T, kase = 0; cin >> T;
    while (T--) {
        cin >> n;
        fill(bit, bit+n+1, 0);
        for (int i = 1; i <= n; ++i) {
            int x; cin >> x; add(i, x);
        }
        cout << "Case " << ++kase << ":\n";
        string op;
        while (cin >> op, op != "End") {
            int x, y; cin >> x >> y;
            if (op == "Add") add(x, y);
            else if (op == "Sub") add(x, -y);
            else cout << sum(y) - sum(x-1) << '\n';
        }
    }
    return 0;
}

複雜度

單次操作 O(log n)，總 O((n+q) log n)，比線段樹常數更小。