# 差分前綴和

* **用來算區間和，以及修改區間值**
* 令一序列為$A_1, A_2, ..., A_n$，其差分$D_i$為$A_i-A_{i-1}$
* 求差分序列的前綴和即為原序列($A_{i-1}+(A_i-A_{i-1})=A_i$)
* 如果要在$A_l$到$A_N$全部加上$x$，只需要在$D_l$加上$x$，再求其前綴和就可以了，因為在$D_l$~$D_n$的前綴和都會包含到$D_l$(前綴和是由左往右)。
* 相同的如果只要在$[l, r]$加$x$，就在$D_l$加$x$，$D_r$減$x$，所以前綴和在$D_l$加了$x$後，又在$D_r$減掉$x$而恢復原來數字。

int n, m; // n:length of array    m:amount of modify
cin >> n >> m;
vector<int> val(n+2, 0);
rep(0,m){
    int a, b, x;
    cin >> a >> b >> x;// [l,r] add x
    val[a]+=x;
    val[b+1]-=x;
}
rep(1,n+1){
    val[i]+=val[i-1]; // 算其前綴合並還原為原序列
}

---