【一维前缀和及一维差分】 <-- 洛谷 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
