HDOJ 1556：差分陣列巧解區間統計，告別線段樹超時

在解決 HDOJ 1556 這道題目時，最直觀的做法是對每個區間直接遍歷累加，但這種 O(n²) 的複雜度必定會導致超時。網上常見的題解動輒引入線段樹等高級數據結構，對於初學者來說既晦澀又難以靈活運用。其實，這道題有一個極其優雅且高效的解法——差分陣列（累加思想），只需幾行代碼即可輕鬆搞定。

核心思路：差分陣列與前綴和

給定一個閉區間 [a, b]，我們希望區間內所有位置的值都加 1。若直接操作數組，效率極低。差分陣列的技巧在於：

• 在起點 a 處 sum[a]++，標記從 a 開始往後所有位置需 +1；
• 在終點下一位 b+1 處 sum[b+1]--，抵消 b 之後位置多加的 1。

最後對 sum 數組做一次前綴和累加，ans[i] = ans[i-1] + sum[i]，即可得到每個位置實際被覆蓋的次數。這將區間更新的時間複雜度從 O(n) 降為 O(1)，整體複雜度變為 O(n)，完美避開超時。

代碼實現

#include <iostream>
#include <cstdio>
#define N 100001
using namespace std;

int main() {
    int n;
    while (scanf("%d", &n) && n != 0) {
        int sum[N] = {0};
        int l, r;
        for (int i = 0; i < n; i++) {
            scanf("%d%d", &l, &r);
            sum[l]++;
            sum[r + 1]--;
        }
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            ans += sum[i];
            printf("%d", ans);
            if (i != n) putchar(' ');
        }
        putchar('\n');
    }
    return 0;
}

為何這比線段樹更適合？

線段樹雖然強大，但代碼量大、常數因子高、易出錯。差分陣列利用了「區間增量轉化為點更新 + 前綴和還原」的數學特性，代碼極短、邏輯清晰、運行極快，是解決此類區間統計問題的利器。掌握這一思想，能讓你在面對大量區間操作時游刃有餘。