HDU 1542 Color the Ball：樹狀數組區間更新單點查詢經典應用

問題描述

N 個氣球排成一行（N ≤ 100,000）。N 次操作，每次給區間 [a, b] 所有氣球塗一次色（a ≤ b）。最終輸出每個氣球被塗色次數。多測試用例，N=0 結束。

核心技巧：差分數組 + 樹狀數組

區間加 1，單點查詢。差分思想：

• 區間 [a, b] 加 1 ⟺ diff[a] += 1, diff[b+1] -= 1
• 前綴和還原：color[i] = Σ_{j=1}^i diff[j]

用樹狀數組維護 diff 陣列，支持 O(log N) 更新/查詢。

樹狀數組實現

#include <cstdio>
#include <cstring>

const int MAXN = 100005;
int bit[MAXN];

int lowbit(int x) { return x & -x; }

void add(int idx, int val, int n) {
    for (; idx <= n; idx += lowbit(idx))
        bit[idx] += val;
}

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

int main() {
    int n, a, b;
    while (scanf("%d", &n) == 1 && n) {
        memset(bit, 0, sizeof(bit));
        for (int i = 1; i <= n; ++i) {
            scanf("%d%d", &a, &b);
            add(a, 1, n);
            add(b + 1, -1, n);
        }
        for (int i = 1; i <= n; ++i) {
            if (i > 1) putchar(' ');
            printf("%d", sum(i));
        }
        putchar('\n');
    }
    return 0;
}

關鍵點解析

1. 差分轉區間操作：將區間加法轉為兩次單點更新
2. b+1 邊界：注意 `b+1` 可能超過 n，`add` 函數內 `idx <= n` 自然截斷
3. 多測試用例：每次 `memset` 清零 BIT 陣列
4. 輸出格式：空格分隔，行末無多餘空格

複雜度

• 每次操作：O(log N)
• 總時間：O(N log N)
• 空間：O(N)

延伸：區間更新區間查詢

若需區間求和，需雙 BIT 或線段樹。本題單點查詢，單 BIT 即可。