前綴和與差分陣列詳解

如果你的解法在陣列題上逾時，修復的關鍵往往不是更花俏的資料結構，而是一個簡單的思路：預處理一次，然後瞬間作答。

為此最可靠的兩件工具，就是前綴和及其鏡像——差分陣列。兩者結合，能讓你回答區間求和問題、套用區間更新，速度遠超樸素做法。它們是競賽程式設計中的前綴和練習的基礎主題，在 BIAA 我們很早就教授它們，因為它們能解鎖大量題目，同時為日後學習更重的資料結構建立直覺。

前綴和到底是什麼

給定一個陣列 arr，前綴和陣列 P 儲存的是累計總和：P[i] 等於 arr[0] + arr[1] + ... + arr[i]。你只需從左到右掃描一遍即可建構，因此建構耗費 O(n) 時間。

回報在於查詢。從索引 l 到 r 的任意連續區間之和，就是：

sum(l, r) = P[r] - P[l - 1]

這是一次常數時間、O(1) 的查找。你不必為每個問題重新累加元素，只需做一次預處理，然後瞬間回答每次查詢。如果一道題詢問 q 次區間求和，你的總工作量就從大約 O(n 乘以 q) 降到 O(n + q)。

前綴和出現的場景

• 在固定陣列上進行區間求和查詢。
• 計數與頻率問題，包括利用餘數統計其和具有某種性質的子陣列。
• 二維前綴和，將同樣的思路擴展到網格，從而能在常數時間內對任意矩形求和。
• 當更新進入視野後，它是邁向線段樹和樹狀陣列（BIT）的墊腳石。

差分陣列：逆向的前綴和

差分陣列是前綴和的逆運算。前綴和把陣列變成累計總和，而差分陣列 D 儲存的是差值：D[i] = arr[i] - arr[i - 1]。對 D 取前綴和即可重建原陣列。

正是這種逆向關係讓區間更新變得廉價。假設你必須給區間 [l, r] 中的每個元素加上一個值 v。樸素做法是每次更新 O(n)。而用差分陣列，你只需觸碰兩個位置：

1. 在索引 l 處加上 v。
2. 在索引 r + 1 處減去 v。

現在每次更新都是 O(1)。記錄完所有更新後，你對 D 跑一次前綴和即可還原最終陣列。處理 Q 次更新加上最後一遍掃描，是 O(Q + n)。

為何這些技能對競賽至關重要

在像 USACO 這樣的平台上，前綴和與差分陣列是 Silver 組別的核心內容。競賽評測機施加嚴格的時間限制，因此一個邏輯正確卻為 O(n 乘以 q) 的迴圈仍可能失敗，而 O(n + q) 的版本則能從容通過。辨識出一道題何時可歸結為「多次區間求和」或「多次區間加」，正是評測者所獎賞的技能。

官方 USACO 分為 Bronze、Silver、Gold 和 Platinum 四個組別。參賽資格、比賽時間窗口和晉級門檻各不相同，因此請務必在競賽中心和 USACO 官方網站確認最新細節，而不要依賴逐年變動的數字。

行之有效的練習計畫

• 從零實作一維前綴和，然後用暴力迴圈校驗 sum(l, r)。
• 用差分陣列解決一道經典的「給區間加值」問題，並確認重建後的陣列。
• 把這兩種思路擴展到二維網格。
• 對比執行時間，讓提速變得具體可感，而非只停留在理論上。

這些技巧是我們建構競賽程式設計專案的核心：學生先學會模式，在小規模輸入上驗證，再在競賽壓力下加以運用。如果你的孩子正在備戰 USACO，或希望打下更扎實的演算法基礎，歡迎了解 BIAA 的競賽程式設計方向，在有指導的練習與回饋中開始建構這些技能。