C++ 前綴和與差分

前綴和

• 陣列前n項的和。
• b[i] = a[0] + a[1] + a[2] + … + a[i]
• 區間和 [l, r]：b[r]-b[l-1] (要保留b[l]所以-1)

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

差分

• 用途：在區間 [l, r] 加上一個數字v。
• b[l] += v; //b[0~l] 加上v
• b[r+1] -= v; //b[r+1~n] 減去v (b[r] 仍保留v)
• 給的 a[] 是前綴和數列，建構 b[]，因為 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;
    cin >> n;
    for(int i=1; i<=n; i++){
        cin >> a[i];
        b[i] = a[i] - a[i-1]; //建構差分數列
    }
    cin >> l >> r >> v;
    b[l] += v;
    b[r+1] -= v;
    
    for(int i=1; i<=n; i++){
        b[i] += b[i-1];
        cout << b[i] << ' ';
    }
}