【題目來源】
https://www.acwing.com/problem/content/799/

【題目描述】
輸入一個長度為 n 的整數序列。
接下來輸入 m 個操作，每個操作包含三個整數 l,r,c，表示將序列中 [l,r] 之間的每個數加上 c。
請你輸出進行完所有操作后的序列。

【輸入格式】
第一行包含兩個整數 n 和 m。
第二行包含 n 個整數，表示整數序列。
接下來 m 行，每行包含三個整數 l，r，c，表示一個操作。

【輸出格式】
共一行，包含 n 個整數，表示最終序列。

【數據范圍】
1≤n,m≤100000,
1≤l≤r≤n,
?1000≤c≤1000,
?1000≤整數序列中元素的值≤1000

【輸入樣例】
6 3
1 2 2 1 2 1
1 3 1
3 5 1
1 6 1

【輸出樣例】
3 4 5 3 4 2

【算法分析】
● 構建差分數組
設原數組為含有 n 個數的 a 數組（下標常從 1 開始），差分數組為 d 數組（下標常從 1 開始）。則令 d[1]=a[1]，d[i]=a[i]-a[i-1]。其中，i∈[2,n]。
● 關鍵操作 d[le]+=x，d[ri+1]-=x
利用差分處理此類“多次對區間進行加減操作”的問題，可以大大降低算法的時間復雜度。這是因為，構造差分數組后，對原數組區間 [le, ri] 的加減操作就轉化為對差分數組的區間端點的操作：d[le]+=x，d[ri+1]-=x。這明顯大大降低了計算量，所以算法效率會很高。注意：此處的原數組及差分數組的下標都從1開始。
● 若已知差分數組 d[i]，則由語句 d[i]+=d[i-1]?可得到原始數組。其中，i∈[1,n]。

【算法代碼】

#include <bits/stdc++.h>
using namespace std;const int N=1e5+5;
int a[N]; //Primitive array
int d[N]; //Difference arrayint main() {int n,m;cin>>n>>m;for(int i=1; i<=n; i++) { //i from 1cin>>a[i];d[i]=a[i]-a[i-1]; //Building a difference array}int le,ri,c;while(m--) {cin>>le>>ri>>c;d[le]+=c;d[ri+1]-=c;}for(int i=1; i<=n; i++) { //i from 1a[i]=d[i]+a[i-1];cout<<a[i]<<" ";}return 0;
}/*
in:
6 3
1 2 2 1 2 1
1 3 1
3 5 1
1 6 1out:
3 4 5 3 4 2
*/

【參考文獻】
https://blog.csdn.net/hnjzsyjyj/article/details/139855105
https://www.acwing.com/solution/content/26588/








?