# 前綴和&貪婪
## 前綴和
例題:有長度為$n$的陣列$x_1,x_2...x_n$，$q$筆詢問求區間和$\sum_{i=l}^rx_i$

解:每次詢問就把 $l$ 到 $r$ 加一遍，複雜度$O(nq)$，顯然不是個好方法
如果我們訂一個前綴和數列$p_i=\sum_{k=1}^ix_k$，那麼區間和$\sum_{i=l}^rx_i$就會等於$p_r-p_{l-1}$，複雜度$O(n+q)$

練習:[模板題](https://cses.fi/problemset/task/1646)

## 差分
前綴和的逆運算，訂差分數列$b_i=x_i-x_{i-1}$，那麼差分數列的前綴和就會是原數列。差分數列可以在$O(1)$區間加值(整個區間增加定值)，但是要查詢某項的值則需$O(n)$

ex.將 $l$ 到 $r$ 加$5$，只需將$b_l+5$及$b_{r+1}-5$

## 貪婪
greedy，顧名思義，就是每次都做出最好的選擇，非常直覺

例題:有{50,10,5,1}四種硬幣，用最少的硬幣數湊出$n$

解:顯然，我們必須先用最大的硬幣，因為那看起來是最好的選擇。如果有73元，就用50+10+10+1+1+1

但是，要思考同樣的策略是否在任何情況都適用
假如有{50,26,10,5,1}五種硬幣，我們需要73元，如果用剛剛的解法會用到6個硬幣，但26+26+10+10+1只需要5個

### 經典問題
#### 不重疊區間

有$n$個活動，你知道各個活動的開始和結束時間，最多可以參加幾個活動?


解:對於每個可以參加的活動，選擇結束時間最早的，這樣就有更多的時間參加下一個活動

int cur_time=0,ans=0;
for(int i=0;i<n;i++){
    if(v[i].first>=cur_time){ //first為活動開始時間
        ans++;
        cur_time=v[i].second; //second為活動結束時間
    }
}

練習[cses:Movie Festival](https://cses.fi/problemset/task/1629)

#### 最大區間和
長度為$n$的陣列，選一段區間使其和最大

[圖源](https://majorli.github.io/algo_guide/ch02/sec02/223_kadanes_algo.html)

解:從1跑到n，如果目前的值小於0就捨棄，否則就把下一項加進來

for(int i=0;i<n;i++){
    cur_val+=v[i];
    cur_max=max(cur_max,cur_val);
    if(cur_val<0){
        cur_val=0;
    }
}

如果現在加到的val是負的，那麼比起val加上下一項，不如直接讓val等於下一項來的大

練習[cses:Maximum Subarray Sum](https://cses.fi/problemset/task/1643/)