原本要講區間 DP，結果發現忘了先講前綴和，在此補上。

前綴和最原始的題目是這樣的：給你長度 n 數列和 q 個 l, r，回答這些 a[l]+...+a[r] 的答案。
最暴力的做法是 O(nq)，兩者都到 10^6 會超時。
解法是我們可以先計算數組的前綴和，也就是在 index i 前面所有數字的和。

sum[0] = 0;
for (int i = 1; i <= n; i++){
    sum[i] = sum[i - 1] + a[i];
}

而 a[l]+...+a[r] 就是 sum[r] - sum[l - 1]。如此可透過前處理，達到 O(n+q) 的複雜度。
基本上，+,*,xor 等可恢復的運算都能用前綴和，如果遇到 min/max 就不行了。

例題

CSES 1662

把所有連續和看成前綴和之差，把題目要求看成找 l, r 滿足 (sum[r] - sum[l - 1]) % n == 0。
因此，算出前綴和後，讓它們 mod n，尋找數值相同 index pair 數量。

CSES 2186

這跟上一題很像，只是必須記錄每個字母出現次數的前綴和，判斷是否某兩個 index 所有字母數量差一樣。

這題字母不多，才能套用此解法。如果字母改成數字並有 10^5 個，可考慮使用 rolling hash，詳細我就不講了。

其他題目

• USACO Introduction to Prefix Sums
• Atcoder Regular Contest 104B
• Codeforces 835C (二維前綴和)
• Atcoder Regular Contest 89D