HDU 1166 敵兵布陣：線段樹單點更新區間查詢經典模板

問題描述

N (≤50000) 個營地，初始人數 given。支持 4 種操作（≤40000 次）：

• Add i j：第 i 營地增加 j 人
• Sub i j：第 i 營地減少 j 人
• Query i j：查詢區間 [i, j] 總人數
• End：結束本測資

多組測資，輸出格式 Case k: 後跟查詢結果。

線段樹結構

每個節點存儲：l, r 區間範圍，val 區間和。
數組大小 4*N 足夠（N=50000 → 200000）。

核心操作

1. 建樹 build(rt, l, r)：遞歸構建，葉子賦初值，內部節點 val = left.val + right.val。
2. 單點更新 update(rt, idx, delta)：遞歸到葉子加 delta，回溯更新祖先 val。
3. 區間查詢 query(rt, L, R)：標準區間查詢，三種情況：完全覆蓋、左子樹、右子樹、橫跨兩側。

參考代碼（C++）

#include 
using namespace std;
const int MAXN = 50050;

struct Node { int l, r, val; } seg[MAXN * 4];
int a[MAXN];

void build(int rt, int l, int r) {
    seg[rt].l = l; seg[rt].r = r;
    if (l == r) { seg[rt].val = a[l]; return; }
    int mid = (l + r) >> 1;
    build(rt<<1, l, mid);
    build(rt<<1|1, mid+1, r);
    seg[rt].val = seg[rt<<1].val + seg[rt<<1|1].val;
}

int query(int rt, int L, int R) {
    if (seg[rt].l == L && seg[rt].r == R) return seg[rt].val;
    int mid = (seg[rt].l + seg[rt].r) >> 1;
    if (R <= mid) return query(rt<<1, L, R);
    if (L > mid) return query(rt<<1|1, L, R);
    return query(rt<<1, L, mid) + query(rt<<1|1, mid+1, R);
}

void update(int rt, int idx, int delta) {
    if (seg[rt].l == seg[rt].r) { seg[rt].val += delta; return; }
    seg[rt].val += delta;
    int mid = (seg[rt].l + seg[rt].r) >> 1;
    if (idx <= mid) update(rt<<1, idx, delta);
    else update(rt<<1|1, idx, delta);
}

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 >> a[i];
        build(1, 1, n);
        cout << "Case " << cas << ":\n";
        string op;
        while (cin >> op, op != "End") {
            int i, j; cin >> i >> j;
            if (op == "Query") cout << query(1, i, j) << '\n';
            else if (op == "Add") update(1, i, j);
            else if (op == "Sub") update(1, i, -j);
        }
    }
    return 0;
}

關鍵細節

• 輸入操作名為字符串，用 cin >> op 讀取，End 結束循環。
• 更新時 Add 正增量，Sub 負增量，統一調用 update。
• 查詢結果保證在 int 範圍內，無需 long long。
• 遞歸深度 ≤ log2(50000) ≈ 16，棧安全。

複雜度

建樹 O(N)，單次更新/查詢 O(log N)，總操作 40000，極快。

總結

HDU 1166 是線段樹「單點更新、區間查詢」的標準模板題。掌握建樹、更新、查詢三大核心遞歸函數，注意區間中點計算與邊界分情況，即可輕鬆 AC。此模板可直接應用於所有區間和/最值/計數等單點修改問題。