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 a[1000], b[1000];
//a:原數列, b:前綴和數列

int main(){
    int n;
    cin >> n; //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] << '\n';
}

/**
10
1 2 3 4 5 6 7 8 9 10
1 3 6 10 15 21 28 36 45 55
2 5
18
**/

差分

  • 用途:在區間 [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] << ' ';
    }
}
分享文章!
發佈留言

發佈留言必須填寫的電子郵件地址不會公開。