前缀和定义

前缀和用途

练习题1：一维前缀和练习

题解：

/*
p_prefixsum_1.cpp  v1.0.0
一维前缀和算法 scanf,print版 
in
5 3
2 1 3 6 4
1 2
1 3
2 4
out
3
6
10
*/
#include <iostream>
using namespace std;
const int N=100010;
int a[N],s[N];              //默认初始化为0 
int main() {
    int n,m;                //n个整数，m个询问 
    cin>>n>>m;
    for (int i=1;i<=n;i++)  //原数组，从1开始 
		cin>>a[i];
    for (int i=1;i<=n;i++) 
	    s[i]=s[i-1]+a[i];   			//公式1 
    while (m--)
    {
        int l, r;
        cin>>l>>r;
        cout<<(s[r]- s[l-1])<<endl;    //公式2
    }
    return 0;
}


/*
p_prefixsum_1.cpp  v1.0.0
一维前缀和算法 scanf,print版 
in
5 3
2 1 3 6 4
1 2
1 3
2 4
out
3
6
10

#include <cstdio>
const int N=100010;
int a[N],s[N];              //默认初始化为0 
int main() {
    int n,m;                //n个整数，m个询问 
    scanf("%d%d", &n, &m);
    for (int i=1;i<=n;i++)  {//原数组，从1开始 
		scanf("%d",&a[i]);
	    s[i]=s[i-1]+a[i];   //前缀和数组，从1开始  公式1
    }
    while (m--)
    {
        int l, r;
        scanf("%d%d", &l, &r);
        printf("%d\n", s[r]- s[l-1]);			 //公式2 
    }
    return 0;
}
*/

/*
暴力枚举法  80分，20分TLE 
复杂度O(m*n)，当m、n大时，必然超时
因为存在重复计算，比如1 ~ K 

#include <iostream>
using namespace std;
const int N=1e5+10;
int a[N];
int main()
{
	int n,m;
	cin>>n>>m;
	for (int i=1;i<=n;i++) cin>>a[i];
	while (m--)
	{
		int l,r;
		cin>>l>>r;
		int sum=0;
		for (int i=l;i<=r;i++)
			sum+=a[i];
		cout<<sum<<endl;
	}
} 
*/