差分
2026-08-27 19:03:06
发布于：上海
24阅读
0回复
0点赞
差分：能通过O(1)的时间复杂度，进行区间修改。
核心思想：通过预处理，维护差分数组。 d[i]=a[i]-a[i-1]
区间修改操作，假设要将[l,r]加上v: d[l]+=v,d[r+=1]-=v
还原原数组：a[i]=a[i-1]+d[i]
例题：
#include<bits/stdc++.h>
using namespace std;
int s[10005],b[10005],t[10005];
int a[10005],d[10005];
int ans;
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>s[i]>>t[i]>>b[i];
a[s[i]]+=b[i];
a[t[i]+1]-=b[i];
}
for(int i=1;i<=1000;i++){
d[i]=d[i-1]+a[i];
ans=max(ans,d[i]);
}
cout<<ans;
return 0;
}
有帮助，赞一个