HDU 1166 敵兵布陣：樹狀數組與線段樹區間和單點修改

題目

N ≤ 50000 營地初始兵力，Q ≤ 40000 次操作：Add i v、Sub i v、Query l r、End。多測資，輸出 Case k:。經典單點修改區間和。

樹狀數組

int bit[MAXN];
void add(int i, int v) { for(; i<=n; i+=i&-i) bit[i] += v; }
int sum(int i) { int s=0; for(; i>0; i-=i&-i) s+=bit[i]; return s; }
int query(int l, int r) { return sum(r) - sum(l-1); }

線段樹

void build(int o, int L, int R) {
    if (L==R) { seg[o]=a[L]; return; }
    int M=(L+R)>>1;
    build(o<<1,L,M); build(o<<1|1,M+1,R);
    seg[o]=seg[o<<1]+seg[o<<1|1];
}
void update(int o, int L, int R, int pos, int val) {
    if (L==R) { seg[o]=val; return; }
    int M=(L+R)>>1;
    if (pos<=M) update(o<<1,L,M,pos,val);
    else update(o<<1|1,M+1,R,pos,val);
    seg[o]=seg[o<<1]+seg[o<<1|1];
}
int query(int o, int L, int R, int l, int r) {
    if (l<=L && R<=r) return seg[o];
    int M=(L+R)>>1, ans=0;
    if (l<=M) ans+=query(o<<1,L,M,l,r);
    if (r>M) ans+=query(o<<1|1,M+1,R,l,r);
    return ans;
}

完整主程式框架

int main() {
    int T; scanf("%d", &T);
    for (int cas=1; cas<=T; ++cas) {
        scanf("%d", &n);
        for (int i=1; i<=n; ++i) scanf("%d", &a[i]);
        build(1,1,n); // 或 BIT 初始化
        printf("Case %d:\n", cas);
        char op[10];
        while (scanf("%s", op), op[0]!='E') {
            int x,y; scanf("%d%d", &x,&y);
            if (op[0]=='A') update(x, y); // Add
            else if (op[0]=='S') update(x, -y); // Sub
            else printf("%d\n", query(x,y)); // Query
        }
    }
}

比較

• 樹狀數組代碼更短、常數更小、適合單點修改區間和。
• 線段樹擴展性強（區間修改、區間最值等）。