NYIST 116：士兵殺敵（二） - 樹狀數組 (Fenwick Tree) 入門

題目描述

有 N 名士兵，初始殺敵數已知。支持兩種操作：

1. 查詢 Q m n：輸出第 m 到第 n 號士兵的殺敵總和。
2. 更新 U i q：第 i 號士兵新增 q 殺敵。

N, M ≤ 10^5，需高效處理。

樹狀數組核心原理

樹狀數組利用 lowbit(x) = x & (-x) 維護前綴和，支持 O(log N) 單點更新與區間查詢。

• update(i, delta)：從 i 向上跳躍更新所有包含該位置的節點。
• query(i)：從 i 向下跳躍累加前綴和。
• 區間和 [l, r] = query(r) - query(l-1)。

代碼實現

#include <cstdio>
#include <cstring>
#define MAXN 1000005
#define lowbit(x) ((x) & (-(x)))

int tree[MAXN];
int N, M;

void update(int idx, int val) {
    for (; idx <= N; idx += lowbit(idx))
        tree[idx] += val;
}

int query(int idx) {
    int sum = 0;
    for (; idx > 0; idx -= lowbit(idx))
        sum += tree[idx];
    return sum;
}

int main() {
    while (scanf("%d%d", &N, &M) == 2) {
        memset(tree, 0, sizeof(tree));
        for (int i = 1; i <= N; ++i) {
            int v; scanf("%d", &v);
            update(i, v);
        }
        char op[2];
        for (int i = 0; i < M; ++i) {
            int x, y; scanf("%s%d%d", op, &x, &y);
            if (op[0] == 'Q')
                printf("%d\n", query(y) - query(x-1));
            else
                update(x, y);
        }
    }
    return 0;
}

複雜度分析

• 構建：O(N log N)（或 O(N) 線性構建）。
• 單次操作：O(log N)。
• 總體：O((N+M) log N)，輕鬆通過。

總結

本題是樹狀數組的標準模板題，掌握 lowbit、更新、查詢三個核心函數即可。適用於靜態區間和、動態單點修改場景。