前缀和XP02笔记
2026-08-03 11:22:47
发布于：浙江
8阅读
0回复
0点赞
前缀和是枚举优化之一，可以吧O(n²)拉到O（n）,前缀和生成代码如下
#include<bits/stdc++.h>
using namespace std;
int a[100005];//10⁵大小
int s[100005]
int main(){
int n;
cin>>n;
for(int i =1;i<=n;i++){
cin>>a[i];
s[i] = s[i-1]+a[i];
}
}
小蚂蚁吃米1代码
#include<bits/stdc++.h>
using namespace std;
int a[100005];
long long s[1000005];
int main(){
int n;
cin>>n;
for(int i =1;i<=n;i++){
cin>>a[i];
s[i] = s[i-1]+a[i];
}
int x;
cin>>x;
cout<<s[x];
}
小蚂蚁吃米2：
#include<bits/stdc++.h>
using namespace std;
int a[100005];
long long s[1000005];
int main(){
int n;
cin>>n;
for(int i =1;i<=n;i++){
cin>>a[i];
s[i] = s[i-1]+a[i];
}
int q;
cin>>q;
for(int i =1;i<=q;i++){
int x;
cin>>x;
cout<<s[x]<<endl;}
}
小蚂蚁吃米3：
#include<bits/stdc++.h>
using namespace std;
int a[100005];
long long s[1000005];
int main(){
int n;
cin>>n;
for(int i =1;i<=n;i++){
cin>>a[i];
s[i] = s[i-1]+a[i];
}
int q;
cin>>q;
for(int i =1;i<=q;i++){
int l,r;
cin>>l>>r;
cout<<s[r]-s[l-1]<<endl;}
}
前缀和区间求和：
s[r]-s[l-1];
这里空空如也
有帮助，赞一个