---
# System prepended metadata

title: difference array  差分
tags: [程設班講義]

---

# 簡介
用更快的速度修改數列區間的值，能把時間複雜度壓低。

開兩個陣列 `a[]` 和 `dif[]`，`a` 儲存原數列，`dif` 儲存差分數列。

前綴和適合查詢區間和 ; 差分適合修改區間值。

如果你全都要，可以結合線段樹。(應該不會講到。)

![未命名](https://hackmd.io/_uploads/r1DlTwXcke.png)

重點在於"**相對**"，改變某區間的值，他內部不會相對改變，但是他和外部連接處會相對改變。

# 程式碼
```cpp=
#include <bits/stdc++.h>
using namespace std ;

int a[11] , dif[12] ;

int main() {
    for (int i = 1 ; i <= 10 ; i++) {
        cin >> a[i] ;
    }
    
    while (1) {
        int l , r , x ;
        cin >> l >> r >> x ;
        dif[l] += x ;
        dif[r + 1] -= x ;
            
        for (int i = 1 ; i <= 10 ; i++) {
            dif[i] += dif[i - 1] ;
            a[i] += dif[i] ;
        }

	fill(dif, dif + 12, 0) ;

        for (int i = 1 ; i <= 10 ; i++) {
            cout << a[i] << " " ;
        }
        cout << endl;
    }
}
```

# 例題
沒有例題，所以我肯定會出一題練手的。

###### 都看到這了難道不按個愛心支持一下嗎?