## 前綴和

功能:可求出任意區間的總和

經典問題：
給一個長度為N的序列a,有Q筆詢問,第i筆詢問為求[l,r]的總和

暴力解
針對每一次查詢都去做加總
複雜度為O(NQ)

#include <iostream>
using namespace std;
int main(){
    int n;
    cin >> n;
    int a[n+1];
    for(int i = 1; i <= n; i++) cin >> a[i];
    int q, l, r;
    cin >> q;
    while(q--){
        cin >> l >> r;
        int sum = 0;
        for(int i = l; i <= r ;i++) sum += a[i];
        cout << sum << "\n";
    }
}

sum[i] = 陣列前i項的和
sum[i] = a[1] + a[2] + … + a[i]
與前項關係 -> sum[i] = sum[i-1] + a[i]
區間和 [l, r]：a[l] +a[l+1] + ... + a[r]
= sum[r]-sum[l-1] (要保留a[l]所以-1)

前綴和預處理
O(N+Q)

#include <iostream>
using namespace std;
int main(){
    int n;
    cin >> n;
    int a[n+1], sum[n+1]={0};
    for(int i=1; i<=n; i++) cin >> a[i];
    for(int i=1; i<=n; i++) sum[i] = sum[i-1] + a[i];
    int q, l, r;
    cin >> q;
    while(q--){
        cin >> l >> r;
        cout << sum[r] - sum[l-1] << "\n" ; //區間和        
    }
}

練習題
zj:e339

帶修改的版本->BIT,線段樹

---

### 二維前綴和

待補

---

## 差分

可以把它想成前綴和的逆運算

定義：任意兩個相鄰值相減形成差的簡稱
如序列｛1、5、6｝的差分序列為｛4、1｝

用途：在區間 [l, r] 加上一個數字v

經典問題：
給一個長度為N的序列a,有Q筆改值,求第K項

實作：
a -> 前綴和數列, b -> 差分數列
b[l] += v; //b[0~l] 加上v
b[r+1] -= v; //b[r+1~n] 減去v (b[r] 仍保留v)

a[i] = b[0] + b[1] + b[2] + … + b[i](前綴和)
所以 b[i] = a[i] – a[i-1]
在 b[l] 加上 v，b[r+1] 減去 v
最後再從 0 跑到 n 使 b[i] += b[i-1]
這樣b 是一個在某區間加上v的前綴和

#include <iostream>
using namespace std;
int a[1000], b[1000];
//a: 前綴和數列, b: 差分數列
int main(){
    int n, l, r, v ,q;
    cin >> n;
    for(int i=1; i<=n; i++){
        cin >> a[i];
        b[i] = a[i] - a[i-1]; //建構差分數列
    }
    cin >> l >> r >> v >> q;
    b[l] += v;
    b[r+1] -= v;
    
    for(int i=1; i<=q; i++){
        b[i] += b[i-1];
    }
    cout << b[q] ;
    

練習

zj:e340