HDU 1166 敵兵布陣：線段樹區間求和與單點增減

問題描述

N (≤50,000) 個營地，初始人數給定。支持 M (≤40,000) 次操作：
Add i j：第 i 營地增加 j 人
Sub i j：第 i 營地減少 j 人
Query i j：查詢區間 [i,j] 總人數
End：本組數據結束

線段樹區別

與 HDU 1754（區間最大值）類似，區別在於：
- 節點值：區間和（而非最大值）
- 合併：sum = left.sum + right.sum
- 更新：val += delta（增量更新）

完整代碼

#include 
using namespace std;
const int MAXN = 50005;
struct SegTree {
    int sum[4*MAXN], L[4*MAXN], R[4*MAXN];
    int a[MAXN];
    void build(int o, int l, int r) {
        L[o]=l; R[o]=r;
        if (l==r) { sum[o]=a[l]; return; }
        int mid=(l+r)/2;
        build(o*2,l,mid); build(o*2+1,mid+1,r);
        sum[o]=sum[o*2]+sum[o*2+1];
    }
    void update(int o, int pos, int delta) {
        if (L[o]==pos && R[o]==pos) { sum[o]+=delta; return; }
        int mid=(L[o]+R[o])/2;
        if (pos<=mid) update(o*2,pos,delta);
        else update(o*2+1,pos,delta);
        sum[o]=sum[o*2]+sum[o*2+1];
    }
    int query(int o, int l, int r) {
        if (l<=L[o] && R[o]<=r) return sum[o];
        int mid=(L[o]+R[o])/2, res=0;
        if (l<=mid) res+=query(o*2,l,r);
        if (r>mid) res+=query(o*2+1,l,r);
        return res;
    }
} st;

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

關鍵細節

1. 輸入操作字符串首字符區分：A/S/Q/E
2. Sub 操作傳入負增量 -y 復用 update
3. 多測試用例，每組輸出 Case i:
4. 線段樹數組開 4×N 保證足夠

複雜度

• 構建：O(N)
• 單次操作：O(log N)
• 總計：O((N+M) log N)

此題是線段樹「區間求和 + 單點增量更新」的標準模板，與區間最值題結構幾乎相同，只需修改合併邏輯與更新方式。