前缀和-入门

Let's go,ak.

2026-02-05 14:50:19

发布于：浙江

7阅读

0回复

0点赞

常见例题

A2479.可莉的蹦蹦炸弹

A336.前缀和

A335.前缀和2

一维前缀和

这是新手经常干的事

#include<bits/stdc++.h>
using namespace std;
int n,m,a[250],b[58];
int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    for(int i=0;i<m;i++){
        int sum=0;
        cin>>b[i];
        for(int j=0;j<b[i];j++){
            sum+=b[i];
        }
        cout<<sum<<endl;
    }
    return 0;
}

时间复杂度O(n²)

遇到0<n<100000000

就原地升天！

前缀和的精华在于——

“提前准备”

#include<bits/stdc++.h>
using namespace std;
int n,m,a[250],b[250],c;
int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++){
        cin>>a[i];
        b[i]=b[i-1]+a[i];
    }
    for(int i=0;i<m;i++){
        cin>>c;
        cout<<b[c]<<endl;
    }
    return 0;
}

时间复杂度O(n);

哪有人会说了：“A336.前缀和不是左右击击吗？”

掐头去尾

#include<bits/stdc++.h>
using namespace std;
long n,m,c,d,a[250000];
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[i]+=a[i-1];
    }
    for(int i=0;i<m;i++){
        cin>>c>>d;
        cout<<a[d]-a[c-1]<<endl;
    }
    return 0;
}