題目：【模板】差分

應用場景：快速解決將某一個區間所有元素加上 “一個數” 的操作。

第一步，預處理差分數組。

f[i] 表示：當前元素與前一個元素的差值? ??a[i] - a[i-1];

但在題目中，我們其實可以不用到a[]這個數組，只使用f[]數組。我們可以先減后加：(易錯)

		LL x; cin >> x;f[i+1] -= x;   //可以不用創建a[]，直接使用f[]  先減后加f[i] += x;

第二步，利用差分數組解決m次修改操作

第三步，如何還原數組？

直接對差分數組做前綴和運算即可。（前面的數變大，后面的數加上前面的數自然會變大）

#include <iostream>using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
LL f[N]; int n, m; int main()
{cin >> n >> m;//有幾個數，有m次操作for (int i = 1; i <= n; i++){LL x; cin >> x;f[i+1] -= x;   //可以不用創建a[]:  先減后加f[i] += x;}while(m--){LL l, r, k; cin >> l >> r >> k;f[l] += k; f[r+1] -= k;} for (int i = 1; i <= n; i++){f[i] = f[i-1] + f[i];cout << f[i] << " ";}return 0;
}

題目：P3406 海底高鐵 - 洛谷

#include <iostream>using namespace std;
const int N = 1e6 + 10;
typedef long long LL;LL f[N];
int n, m;
LL sum = 0;//第二段鐵路連接城市2-3 ，每次單獨購買車票 
//花Ci買卡，乘坐只要扣給Bi元 //N,M  表示N個城市，N-1段鐵路   要訪問M個城市
//M個要訪問的城市
//N-1個單獨車票，買卡，買卡票 int main()
{cin >> n >> m;int x; cin >> x;int y;for (int i = 2; i <= m; i++){cin >> y;if (x > y){f[y]++;f[x]--;}else{f[y]--;f[x]++;}x = y;}for (int i = 1; i <= n; i++){f[i+1] += f[i];}for (int i = 1; i < n; i++){LL a, b, c; cin >> a >> b >> c;sum += min(f[i]*a, c+f[i]*b);}cout << sum << endl; return 0;
}