前綴和加速（prefix-sum speed-ups）

想像你不斷被問「陣列中位置 i 到位置 j 之間的總和是多少？」若你每次都從頭把那一段加起來，單次查詢最多花 O(n)，許多次查詢就變慢。前綴和是一次性的準備，讓每個這種「區間總和」查詢都能以 O(1) 回答。它是最簡單也最普遍的動態規劃加速法：先一次算好累計總和，之後用相減回答無數個區間問題。

建一個陣列 P，其中 P[0] = 0 而 P[k] = a[1] + a[2] + ... + a[k]，即前 k 個元素之和。每個 P[k] 就是 P[k-1] + a[k]，所以整個前綴和陣列以一趟 O(n) 填好——它本身就是一個小動態規劃，遞迴為 P[k] = P[k-1] + a[k]。現在任意連續區間 a[i..j] 之和等於 P[j] - P[i-1]：到 j 為止的累計總和，減去到 i 之前為止的累計總和，恰好剩下中間那塊。不論區間多寬，這個相減都是 O(1)。同樣的想法可推廣到二維（二維前綴和以容斥原理用四次查表回答矩形和查詢）以及其他可反轉的運算。

它改造動態規劃的地方，在於那些「對一段連續的前一狀態求和」的轉移。若 dp[i] =（某個關於）一個窗口內 dp[j] 之和（的函數），樸素地每個 i 花 O(窗口)，整個動態規劃是 O(n 乘以 窗口) 或 O(n^2)；對 dp 值做前綴和則把每個轉移壓成 O(1)，常把 O(n^2) 變成 O(n)。誠實的限制：前綴和需要可反轉的合併——和與互斥或可行，因為你能相減或相消，但純粹的 max「不行」（你無法把已取的最大值收回），所以區間最大值需要稀疏表或線段樹這類不同的結構。此外，前綴和假設陣列是靜態的；若底層數值在查詢之間會改變，純粹的前綴和就過時了，你得改用樹狀陣列（Fenwick tree）或線段樹。