您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

HDU 1166 敵兵布陣 - 線段樹區間查詢與單點更新模板題

編輯：關於C++

問題描述

有 N 個營地（N ≤ 50,000），初始各有若干士兵。支援三種操作（最多 40,000 次）：

Add i j：第 i 營地增加 j 人
Sub i j：第 i 營地減少 j 人
Query i j：查詢區間 [i, j] 總人數
End：結束當前測試用例

線段樹結構設計

每個節點存儲區間 [l, r] 的和 sum。葉子節點對應單個營地。

struct Node {
    int l, r;   // 區間左右邊界
    int sum;    // 區間和
} tree[MAXN * 4];

核心操作實現

建樹

void build(int l, int r, int idx) {
    tree[idx].l = l; tree[idx].r = r;
    if (l == r) {
        tree[idx].sum = arr[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(l, mid, idx << 1);
    build(mid + 1, r, idx << 1 | 1);
    tree[idx].sum = tree[idx<<1].sum + tree[idx<<1|1].sum;
}

單點更新（增/減）

void update(int pos, int val, int idx) {
    if (tree[idx].l == tree[idx].r) {
        tree[idx].sum += val;  // val 可為正(Add)或負(Sub)
        return;
    }
    int mid = (tree[idx].l + tree[idx].r) >> 1;
    if (pos <= mid) update(pos, val, idx << 1);
    else update(pos, val, idx << 1 | 1);
    tree[idx].sum = tree[idx<<1].sum + tree[idx<<1|1].sum;
}

區間查詢

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

完整主程序

#include 
#include 
#include 
using namespace std;

const int MAXN = 50010;
struct Node { int l, r, sum; } tree[MAXN * 4];
int arr[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T; scanf("%d", &T);
    for (int cas = 1; cas <= T; ++cas) {
        int n; scanf("%d", &n);
        for (int i = 1; i <= n; ++i) scanf("%d", &arr[i]);
        build(1, n, 1);
        
        printf("Case %d:\n", cas);
        char cmd[10];
        while (scanf("%s", cmd) == 1) {
            if (strcmp(cmd, "End") == 0) break;
            int x, y; scanf("%d%d", &x, &y);
            if (strcmp(cmd, "Add") == 0) update(x, y, 1);
            else if (strcmp(cmd, "Sub") == 0) update(x, -y, 1);
            else if (strcmp(cmd, "Query") == 0) printf("%d\n", query(x, y, 1));
        }
    }
    return 0;
}