#include <iostream> using namespace std; int a[10000005],n,m; int s[10000005]; int main() { cin>>n>>m; for(int i=1; i<=n; i++) { cin>>a[i]; s[i]=s[i-1]+a[i]; } while(m--) { int l,r; cin>>l>>r; cout<<s[r]-s[l-1]<<endl; } return 0; }

#include <iostream> using namespace std; int n,m,num,a[100005]={},sum=0,v=0; int s[100005]={};//前缀和 前缀和 包含当前元素之前的所有元素之和 int main() { cin>>n>>m; for(int i=1;i<=n;i++) { cin>>a[i]; s[i]=s[i+1]+a[i];//预处理前缀和 } for(int i=0;i<m;i++) { cin>>num>>v; sum=0; sum=s[v]+s[num+1]; cout<<sum<<endl; }

首先，输入一次扫一次数组肯定不行，会TLE 因此，用前缀和数组一减就行

#include <iostream> using namespace std; int a[10000005],n,m; int s[10000005]; int main() { cin>>n>>m; for(int i=1; i<=n; i++) { cin>>a[i]; s[i]=s[i-1]+a[i]; } while(m--) { int l,r; cin>>l>>r; cout<<s[r]-s[l-1]<<endl; } return 0; }

> 不得不说，ACGO数据太太太太太太太太太太\tiny太\scriptsize太\footnotesize太\small太\normalsize太\large太\Large太\LARGE太\huge太\Huge太太太太太太太太太太太水了。 拿到题，废话不多说，直接暴力！ 这肯定是不……不儿，AC\color{lightgreen}ACAC啦？ 当然，按常理来说，0≤n,m≤1000000\le n,m\le 1000000≤n,m≤100000的数据O(n2)O(n^2)O(n2)的时间复杂度一定会TLE\color{blue}TLETLE的。 所以，换思路！ 首先，我们先来进食一下“前缀和”的知识点。 第一步，准备一个sum数组，就像这样：int sum[1000005];。 第二步，预处理sum数组，sum[i]就表示a[1]到a[n]这个区间的和。代码：sum[i]=sum[i-1]+a[i]; 接下来怎么计算呢？ 请看图片： 借助这个思路，成功AC\color{lightgreen}ACAC！ 代码：

#include<iostream> using namespace std; int a[100005],s[100005]={0},n,m,R,L; int main(){ cin>>n>>m; for(int i=1;i<=n;++i){ cin>>a[i]; s[i]=s[i-1]+a[i]; } for(int i=1;i<= m;++i){ cin>>R>>L; cout<<s[L]-s[R-1]<<endl; } return 0; }

这题有多种方法。 暴力破解当然是可以的，但可能会超时，所以得用聪明一点的办法！ 具体思路如下： 假设数组为：1 2 3 4 5 先设一个前缀和数组S,求原数组的前缀和 这样就完成了基础操作。 接下来就要用到特殊的办法了： 设我们要求[2]到[4]，其实就是求[1]到[4]减[1] 其实就是s[r]-s[l-1] 即： 下面是完整代码： 求小赞一个。Thanks♪(･ω･)ﾉ

为什么都说要算前缀？？？？？（本人已一头雾水） 输入一次算一次不可以吗？？？？？ 代码如下： 都是AC，也没THE呀！！！！！

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

#include <iostream> using namespace std; int main(){ int a[10000005]; int s[10000005]; int n,m; cin >> n >> m; for(int i=1;i<=n;i++){ cin >> a[i]; s[i]=s[i-1]+a[i]; } for(int y=1;y<=m;y++){ int l,r; cin >> l >> r; cout << s[r]-s[l-1] << endl; } return 0; }

#include<bits/stdc++.h> using namespace std; #define ll long long int a[1000000],p[1000000]; int n,m; int main(){ cin>>n>>m; for(int i=1;i<=n;i++){ cin>>a[i]; p[i]=p[i-1]+a[i]; } while(m--){ int l,r; cin>>l>>r; cout<<p[r]-p[l-1]<<endl; } return 0; }

前缀和就是把第1项到第i项的和存储在数组里

#include<bits/stdc++.h> using namespace std; int a[1000005]; int p[1000005]; int main(){ int n , q; cin >> n >> q; for(int i = 1;i <= n;i++) cin >> a[i] , p[i] = a[i] + p[i-1]; while(q--){ int l , r; cin >> l >> r; cout << p[r] - p[l-1] << endl; } return 0; }

注意M,N<105M,N<10^5M,N<105 这样会超时： 正解