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] << ' ';
    }
}
發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *