NYoj 228 士兵殺敵（五）：差分數組 + 前綴和解決區間更新查詢

題目大意

有 N 個士兵（編號 0~N），進行 C 次區間軍功增加操作：區間 [Mi, Ni] 每人增加 Ai 軍功。隨後 Q 次查詢：區間 [m, n] 總軍功對 10003 取模。約束：N, C, Q ≤ 1,000,000，Ai ≤ 100。

核心技巧：差分數組 + 雙層前綴和

1. 差分數組處理區間加值

對區間 [a, b] 加 x：

diff[a] += x;
diff[b + 1] -= x;

最終對 diff 做前綴和，即得到每個士兵的軍功值 val[i]。

2. 二次前綴和直接回答區間和查詢

預計算 sum[i] = sum[i-1] + val[i]，則區間 [m, n] 總軍功 = sum[n] - sum[m-1]，O(1) 回答查詢。

完整算法流程

1. 讀入 N, C, Q
2. 初始化 diff 數組（大小 N+2）
3. 處理 C 次更新：diff[Mi] += Ai; diff[Ni+1] -= Ai; 記錄最大下標 maxIdx
4. 計算軍功值：for i=1..maxIdx: val[i] = val[i-1] + diff[i]
5. 計算前綴和：for i=1..maxIdx: sum[i] = (sum[i-1] + val[i]) % MOD
6. 處理 Q 次查詢：輸出 (sum[n] - sum[m-1] + MOD) % MOD

C 語言實現

#include <stdio.h>
#include <string.h>

#define MAXN 1000010
#define MOD 10003

int diff[MAXN];
int sum[MAXN];

int main() {
    int n, c, q;
    memset(diff, 0, sizeof(diff));
    memset(sum, 0, sizeof(sum));
    
    scanf("%d %d %d", &n, &c, &q);
    
    int maxIdx = 0;
    for (int i = 0; i < c; ++i) {
        int a, b, x;
        scanf("%d %d %d", &a, &b, &x);
        diff[a] += x;
        if (b + 1 <= n) diff[b + 1] -= x;
        if (b > maxIdx) maxIdx = b;
    }
    
    // 第一層前綴和：得到每個士兵軍功
    for (int i = 1; i <= maxIdx; ++i) {
        diff[i] += diff[i - 1];
    }
    
    // 第二層前綴和：得到區間和（取模）
    sum[0] = diff[0];
    for (int i = 1; i <= maxIdx; ++i) {
        sum[i] = (sum[i - 1] + diff[i]) % MOD;
    }
    
    // 回答查詢
    for (int i = 0; i < q; ++i) {
        int m, n;
        scanf("%d %d", &m, &n);
        int ans = (sum[n] - sum[m - 1]) % MOD;
        if (ans < 0) ans += MOD;
        printf("%d\n", ans);
    }
    return 0;
}

複雜度分析

• 時間：O(N + C + Q)，線性處理所有操作
• 空間：O(N)，兩個 int 數組約 8MB

關鍵點總結

1. 差分數組：將區間加值轉為兩點修改，O(1) 更新
2. 雙層前綴和：第一層還原單點值，第二層預計算區間和
3. 離線處理：所有更新先攤平，再統一查詢，避免數據結構開銷
4. 模運算：前綴和階段取模防溢出，查詢時注意負數修正

這道題是差分數組 + 前綴和經典應用，將區間更新、區間查詢雙雙壓縮到 O(1)，是大規模數據下的最優解法。