# 前綴和/差分

如果把差分和前綴和視為對序列的操作，那麼差分和前綴和是一對互逆的操作：
對a數列進行差分可以得到d數列
對d數列做前綴和可以得到a數列。
同理:
對s數列進行差分可以得到a數列
對a數列做前綴和可以得到s數列。

差分數列d: $d_i=a_i-a_{i-1};d_1=a_1$
前缀和數列s: $s_i=\sum_{i}^{j=1} a_j$

用一個具體的例子說明

a=[1,5,3,4,2](原始數列)
=>d=[1,4,-2,1,-2](差分數列)
=>s=[1,6,9,13,15](前缀和數列)

小模板(不一定要這樣寫)

int a[N+1],d[N+1],s[N+1];
for(int i=1;i<=N;i++){
    d[i]=a[i]-a[i-1];
}
for(int i=1;i<=N;i++){
    s[i]=s[i-1]+a[i];
}

### 前綴和範例

e346: 區間和練習
https://zerojudge.tw/ShowProblem?problemid=e346

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define inf 2e18
#define maxn 200005
#define mod 1000000007

signed main(){

    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin>>n;
    int arr[maxn];
    arr[0]=0;
    for(int i=1;i<=n;i++){
        cin>>arr[i];
        arr[i]+=arr[i-1];
    }
    int q;
    cin>>q;
    while(q--){
        int l,r;
        cin>>l>>r;
        cout<<arr[r]-arr[l-1]<<endl;
    }
}

codeforces:H1. 區間求和問題 (Range Sum Queries)【One-dimensional Version】
https://codeforces.com/group/H0qY3QmnOW/contest/383582/problem/H1

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define inf 2e18
#define maxn 200005
#define mod 1000000007

signed main(){

    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin>>n;
    int arr[maxn];
    arr[0]=0;
    int sum=0;
    for(int i=1;i<=n;i++){
        int k;
        cin>>k;
        sum+=k;
        arr[i]=sum;
    }
    int q;
    cin>>q;
    while(q--){
        int a,b;
        cin>>a>>b;
        cout<<arr[b]-arr[a-1]<<endl;;
    }
}

### 差分範例

洛谷:P2367 语文成绩
https://www.luogu.com.cn/problem/P2367

因為要在vec上做單點修改
所以先把vec做差分
最後再還原去求最小值

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define inf 2e18
#define maxn 100005
#define mod 1000000007


signed main(){

    ios::sync_with_stdio(0);
    cin.tie(0);

    int n,p;
    cin>>n>>p;
    vector<int>vec(n+2);
    for(int i=1;i<=n;i++){
        cin>>vec[i];
    }
    for(int i=n;i>=1;i--){
        vec[i]=vec[i]-vec[i-1];
    }
    while(p--){
        int l,r,v;
        cin>>l>>r>>v;
        vec[l]+=v;
        vec[r+1]-=v;
    }
    int ans=1e9;
    for(int i=1;i<=n;i++){
        vec[i]+=vec[i-1];
        ans=min(ans,vec[i]);
    }
    cout<<ans;
}