# 連續和相關問題 --- ## 1. 區間求和問題 ---- * 此問題已經在[這裡](https://hackmd.io/@aacp/rk3xLLtNc#/2)提過了 * 進階練習題：[ABC 122 C - GeT AC](https://atcoder.jp/contests/abc122/tasks/abc122_c) --- ## 2. 差分序列 ---- * 給定序列 $a$ (從 $1$ 開始編號)，我們定義序列 $a$ 的<font color="0x00ff00">前綴和序列</font> $S$ 的產生方式為 $s_i = \sum\limits_{j=1}^i a_j$ * 類似的，我們定義 $a$ 的<font color="0xff00ff">差分序列</font> $d$ 產生方式為 $d_i = a_i - a_{i-1}$ (令 $a_0 = 0$) * 兩個性質： 1. 一個序列的<font color="0x00ff00">前綴和序列</font>的<font color="0xff00ff">差分序列</font>就是自己。 2. 一個序列的<font color="0xff00ff">差分序列</font>的<font color="0x00ff00">前綴和序列</font>也是自己。 ---- * 差分序列常用來解以下問題： * 給定一個序列 $a$，長度為 $N$，接著有 $Q$ 個操作，每個操作會給你三個參數 $L_i, R_i, V_i$，請把序列 $a$ 的第 $L_i$ 到 的 $R_i$ 個數字都增加 $V_i$，請輸出所有操作完成後序列 $a$ 的樣子。 * 可做到時間複雜度 $O(N+Q)$。 ---- 範例輸入： ``` 5 3 1 2 3 4 5 2 4 -2 3 5 3 1 4 1 ``` 範例輸出： ``` 2 1 5 6 8 ``` * [參考程式碼](https://gist.github.com/dreamoon4/10d2c34a9459928ae9ce3d1234cc79d4) ---- * 練習題： 1. [Weekly Training Farm 26 B. Power](https://codeforces.com/group/gRkn7bDfsN/contest/212178/problem/B) 2. [ABC183 D - Water Heater](https://atcoder.jp/contests/abc183/tasks/abc183_d) 3. [CF1501 B. Napoleon Cake](https://codeforces.com/problemset/problem/1501/B) ---- * 進階習題：[CF1700 C. Helping the Nature](https://codeforces.com/problemset/problem/1700/C) * 此題乍看之下很複雜，但把每種操作都找出對應的差分序列上的操作，就變簡單囉。 --- ## 3. 連續和相關問題 ---- * 看到題目出現序列中的「連續和」的概念時，不妨先求出原序列的「前綴和序列」，這樣子轉變後，「連續和」的概念就變為某個編號大的數字減去編號小的數字。這樣的轉變常常能幫助我們解題 ---- * 例題一：最大連續和([CSES 1643 Maximum Subarray Sum](https://cses.fi/problemset/task/1643)) * 把它轉換為前綴和序列上的問題就變成 [AP325 P-4-12. 一次買賣](https://judge.tcirc.tw/ShowProblem?problemid=d051) 這題了 ---- * 例題二：[CF 873B. Balanced Substring](https://codeforces.com/problemset/problem/873/B) --- ## 4. xor 連續和 --- ## 5. 二維前綴和 --- ## 6. 二維差分 --- ## 7. 梯形加總問題