【一維前綴和及一維差分知識點】
● 一維“前綴和數組”預處理過程：cin>>a[i],?sum[i]=sum[i-1]+a[i]? 或者? cin>>sum[i],?sum[i]+=sum[i-1]? ?（1≤i≤n）
● 一維“區間和”計算過程：sum[y]-sum[x-1] ? ? ?（y≥x）
● 長度為 k 的區間和的公式為：sum[i]-sum[i-k]
● 一維區間操作轉端點操作?d[le]+=x，d[ri+1]-=x，可以高效地對區間 [le,ri] 內的每個元素都 +x。

（一）一維前綴和
題目來源：https://www.acwing.com/problem/content/797/
代碼來源：https://blog.csdn.net/hnjzsyjyj/article/details/144885387

#include <bits/stdc++.h>
using namespace std;const int maxn=1e5+5;
int a[maxn],s[maxn];int main() {int n,m;scanf("%d%d",&n,&m);for(int i=1; i<=n; i++) {scanf("%d",&a[i]);s[i]=s[i-1]+a[i];}while(m--) {int le,ri;scanf("%d%d",&le,&ri);printf("%d\n",s[ri]-s[le-1]);}return 0;
}/*
in:
5 3
2 1 3 6 4
1 2
1 3
2 4out:
3
6
10
*/

（二）一維差分
題目來源：https://www.acwing.com/problem/content/799/
代碼來源：https://blog.csdn.net/hnjzsyjyj/article/details/139963345

#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
*/

【二維前綴和及二維差分知識點】
● 二維“前綴和數組”預處理過程：sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j]
● 二維“區間和”計算過程：( sum[x2][y2] - sum[x2][y1-1] ) - ( sum[x1-1][y2] - sum[x1-1][y1-1] ) = sum[x2][y2] - sum[x2][y1-1] - sum[x1-1][y2] + sum[x1-1][y1-1] ? ? ? （y2≥y1，x2≥x1）
●?二維區間操作轉端點操作
若二維區域的左上角坐標為 (x1, y1)，右下角坐標為 (x2, y2)，則如下代碼可高效實現對此二維區域內所有元素 +x 的操作。
d[x1][y1]+=x;
d[x1][y2+1]-=x;
d[x2+1][y1]-=x;
d[x2+1][y2+1]+=x;

（一）二維前綴和
題目來源：https://www.acwing.com/problem/content/798/
代碼來源：https://blog.csdn.net/hnjzsyjyj/article/details/144908502

#include <bits/stdc++.h>
using namespace std;const int maxn=1e3+5;
int a[maxn][maxn];
int s[maxn][maxn];int main() {int n,m,q;cin>>n>>m>>q;for(int i=1; i<=n; i++)for(int j=1; j<=m; j++) {scanf("%d",&a[i][j]);s[i][j]=s[i][j-1]+s[i-1][j]-s[i-1][j-1]+a[i][j];}while(q--) {int x1,y1,x2,y2;scanf("%d%d%d%d",&x1,&y1,&x2,&y2);printf("%d\n",s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1]);}return 0;
}/*
in:
3 4 3
1 7 2 4
3 6 2 8
2 1 2 3
1 1 2 2
2 1 3 4
1 3 3 4out:
17
27
21
*/

（二）二維差分
題目來源：https://www.acwing.com/problem/content/800/
代碼來源：https://blog.csdn.net/hnjzsyjyj/article/details/139970246

#include <bits/stdc++.h>
using namespace std;const int maxn=1e3+5;
int a[maxn][maxn];
int d[maxn][maxn];
int n,m,q;int main() {cin>>n>>m>>q;for(int i=1; i<=n; i++) {for(int j=1; j<=m; j++) {cin>>a[i][j];}}for(int i=1; i<=n; i++) {for(int j=1; j<=m; j++) {d[i][j]=a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1];}}while(q--) {int x1,y1,x2,y2,c;cin>>x1>>y1>>x2>>y2>>c;d[x1][y1]+=c;d[x1][y2+1]-=c;d[x2+1][y1]-=c;d[x2+1][y2+1]+=c;}for(int i=1; i<=n; i++) {for(int j=1; j<=m; j++) {a[i][j]=d[i][j]+a[i-1][j]+a[i][j-1]-a[i-1][j-1];}}for(int i=1; i<=n; i++) {for(int j=1; j<=m; j++) cout<<a[i][j]<<" ";cout<<endl;}return 0;
}/*
in:
3 4 3
1 2 2 1
3 2 2 1
1 1 1 1
1 1 2 2 1
1 3 2 3 2
3 1 3 4 1out:
2 3 4 1
4 3 4 1
2 2 2 2
*/

【一維前綴和及一維差分示例】? <--??洛谷 P5638：光騅者的榮耀
題目來源：https://www.luogu.com.cn/problem/P5638
代碼來源：https://blog.csdn.net/hnjzsyjyj/article/details/145251582

#include <bits/stdc++.h>
using namespace std;typedef long long LL;
const int maxn=1e6+5;
LL s[maxn],d[maxn];
LL t;
int n,k;int main() {cin>>n>>k;for(int i=1; i<n; i++) {cin>>s[i];s[i]+=s[i-1];}for(int i=1; i<=n-k; i++) {t=max(t,s[i+k-1]-s[i-1]);}cout<<s[n-1]-t<<endl;return 0;
}/*
in:
4 1
1 2 3out:
3
*/

【二維前綴和及二維差分示例】? <--??洛谷 P3397：地毯
題目來源：https://www.luogu.com.cn/problem/P3397
代碼來源：https://blog.csdn.net/hnjzsyjyj/article/details/145268744

#include <bits/stdc++.h>
using namespace std;const int maxn=1e3+5;
int a[maxn][maxn];
int d[maxn][maxn];
int n,m;int main() {cin>>n>>m;while(m--) {int x1,y1,x2,y2;cin>>x1>>y1>>x2>>y2;for(int i=x1; i<=x2; i++) {d[i][y1]++;d[i][y2+1]--;}}for(int i=1; i<=n; i++) {for(int j=1; j<=n; j++) {a[i][j]=a[i][j-1]+d[i][j];cout<<a[i][j]<<" ";}cout<<endl;}return 0;
}/*
in:
5 3
2 2 3 3
3 3 5 5
1 2 1 4out:
0 1 1 1 0
0 1 1 0 0
0 1 2 1 1
0 0 1 1 1
0 0 1 1 1
*/

【參考文獻】
https://blog.csdn.net/hnjzsyjyj/article/details/145251582
https://blog.csdn.net/hnjzsyjyj/article/details/145268744

?