AcWing 795. 【算法基础课】前缀和    原题链接    简单

作者： 作者的头像   Conan15 ,  2022-06-21 16:32:06 ,  所有人可见 ,  阅读 967

9


$$\color{red}{算法}\color{blue}{基础课}\color{purple}{笔记and题解}\color{green}{汇总}$$
笔记：

  1. 前缀和的作用：可以求区间$l$~$r$的和：

    1. for循环 $O(n)$
    2. 前缀和 $O(n)$，$s_r-s_{l-1}$

  2. 前缀和如何求解

    • for循环。

代码：

#include<bits/stdc++.h>
using namespace std;
int n, m, a[100010];
int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1;i <= n; i++){
        scanf("%d", &a[i]);
        a[i] += a[i-1];
    }
    for(int i = 1;i <= m; i++){
        int x, y; scanf("%d%d", &x, &y);
        cout << a[y] - a[x-1]; puts("");
    }
    return 0;
}

1 评论

用户头像
zeng9999jian   2022-09-25 20:28         踩      回复

我也来打卡~

#include<bits/stdc++.h>
using namespace std;
const int N = 1000010;
int s[N];
int main()
{
    int a,n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a,s[i]=s[i-1]+a;
    while(m--)
    {
        int l,r;
        cin>>l>>r;
        cout<<s[r]-s[l-1]<<endl;
    }
}