前綴和以及差分
前言
在寫CCF的202109-2題目時，我們宿舍的一位大佬教我怎麼使用差分演算法來解那道題，可是在他教了我兩遍之後，我還是不能理解。然後今天去問了老師，老師跟我說他並沒有聽說過什麼差分！嗚嗚嗚，我當場就懵逼了，老師也給我講解了一下他的看法，但是我還是不能明白。就在剛剛，我又想了一想，好像突然之間開竅了，好像就理解了，所以我把那題目寫了之後，我就接著想把我的理解寫出來了，我怕以後我又忘了，又不能理解了，廢話不多說了，開始吧！
先講什麼是前綴和
前綴和，就是這個數字及其前面的數的和，也就是 Sm=a[0]+a[1]+a[2]+···+a[i],（a[0]=0,下面b,c同樣如此）我們把Sm叫做a[i]的前綴和，然後用一個數組來存儲前綴和的話這個數組就叫前綴和數組，例如：
b[i]=a[0]+a[1]+a[2]+···+a[i]
再講差分
差分就是兩數之差，a[i]-a[i-1]，就叫做a[i]的差分，同樣，也會有一個差分數組，c[i]=a[i]-a[i-1]
差分數組的性質
性質一：我們不難發現，差分數組的前綴和就是原數組在當前位置的具體值，你看：
c[1]=a[1]-a[0]
c[2]=a[2]-a[1]
···
c[i]=a[i]-a[i-1]
所以，sum=c[1]+c[2]+···+c[i]=a[i]-a[0]=a[i]
性質二：（不懂怎麼表述）*****
我們先給一個數組吧
a[ ]={0,1,2,3,4,5,6,7,8,9};
現在我要對[2,7]範圍內的元素都進行+5的操作。那我們當然可以一個一個加，但是這樣太麻煩了，我們可以用差分數組來進行操作。設b為a的差分數，則
b[ ]={0,1,1,1,1,1,1,1,1,1};
我們對下標為[2,7]的元素都加上5，那麼對於2到7的元素來說，他們的差分是不會變得，因為大家都加了5，也就是說，+5這個操作影響的是範圍內於範圍外的值的差分，也就是影響的是臨界的時候的差分。
所以，只需對差分數組b[2]+5即可，進行前綴和操作時，2以後的數都會+5,但是我們只是想在[2,7]這個範圍+5,並不想影響到下標7以後的數，所以，我們執行b[8]-5，這時，求前綴和的時候7以後的數還和原來一樣不受影響。
處理後的差分數組：
b[ ]={0,1,7,1,1,1,1,1,-4,1};
求前綴和：
a[ ]={0,1,8,9,10,11,12,8,9};
你看，這不就相當於對下標[2,7]的數都加上了5嘛！
所以，當我們要對一個範圍內的數全體加上或減去某個值時，我們可以對它的差分數組進行操作。具體操作就是：
void add(int l, int r,int n) {
diff[l]+n, diff[r+1]-n;//l為下界，r為上界
}
再來一次，對下標為[1,5]的數全體+1，這時執行
add(1,5,1);
這時：
b[ ]={0,2,7,1,1,1,0,1,-4,1};
a[ ]={0,2,9,10,11,12,12,8,9};
同樣的，無論我們執行多少次操作，我們只要對差分數組進行操作即可，最後在對差分數組求前綴和就能得出最後的結果。這個就是第二個性質。
以CCF-CSP202109-2為例講解
題目詳細見下面的博文
//www.cnblogs.com/yongcheng137blogs/p/15412952.html
#include <iostream>
using namespace std;
const int N = 1e6;
int dif[N], a[N];
int n;
void add(int l, int r) { dif[l]++, dif[r + 1]--; }
int main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) {
if (a[i - 1] < a[i]) {
add(a[i - 1] + 1, a[i]);
}
}
int maxn = 0, pre = 0;
for (int p = 1; p < 1e4; p++) {
pre += dif[p];
maxn = max(maxn, pre);
}
cout << maxn;
return 0;
}
當a[i]>a[i-1]時，當p取到這兩個數之間的值時，這裡會出現一個非零段，也就是非零段加1，這是不是我們上面所說的對一個範圍+某個值？這時候我們執行add(a[i-1]+1,a[i])的意思就是，當p取a[i-1]+1到a[i]這些值的時候，非零段會+1；然後我遍曆數組，對滿足條件的數同樣進行上面的差分操作，也就是
if (a[i - 1] < a[i]) {
add(a[i - 1] + 1, a[i]);
}
到了最後，我們求dif的前綴和pre=dif[0]+dif[1]+···+dif[p]，這樣就可以直接求得dif的最終狀態，也就是pre就是當取值為p時的非零段個數。
pre += dif[p];
然後題目要求求出最大的非零段，用maxn還記錄最大值即可。
