前缀和
问题描述：给定一个长度为n的数组a，有q次询问，每次询问数组a在区间[l,r]的和。
问题来自这：问题 A: 【模板】前缀和 - ETOJ (eriktse.com)
为了方便计算数组从1开始：（a[0]默认为0)
如果需要求的区间为[3,6]，则我们需要先求出[1,2]的和再求出[1,6]的和，用[1,6]的区间和减去[1,2]的区间和，得到目标区间[3,6] 的区间和，如下图：
区间和如下图：
我们有图可以知道p[1]=a[1],p[2]=a[1]+a[2],p[3]=a[1]+a[2]+a[3]==p[2]+a[3].......p[i]=p[i-1]+a[i];推出了区间和的表达式。
求单独区间和的代码如下（[1,1],[1,2].......[1,9])：
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1e5+9;
ll a[N];
ll p[N];//储存区间的和
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n;
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<=n;i++)
p[i]=p[i-1]+a[i];//得到区间和 p[3]就是[1,3]的和
for(int i=1;i<=n;i++)
cout<<'p'<<i<<'='<<p[i]<<'\n';
return 0;
}
运行结果如下图：
得到区间和之后，就可以去计算出[l,r]的区间和。
代码如下：
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1e5+9;
ll a[N];
ll p[N];//储存区间的和
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n;
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<=n;i++)
p[i]=p[i-1]+a[i];//得到区间和 p[3]就是[1,3]的和
for(int i=1;i<=n;i++)
cout<<'p'<<i<<'='<<p[i]<<'\n';
int l,r;
cin>>l>>r;
int ans;
ans=p[r]-p[l-1];
cout<<l<<" 到"<<r<<"的区间和="<<ans<<'\n';
return 0;
}
结合后得到最终的代码如下所示：
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1e5+9;
ll a[N];
ll p[N];//储存区间的和
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n;
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<=n;i++)
p[i]=p[i-1]+a[i];//得到区间和 p[3]就是[1,3]的和
int q=0;
cin>>q;
while(q--)
{
int l,r;
cin>>l>>r;
cout<<p[r]-p[l-1]<<'\n';
}
return 0;
}
由于第一次写，非常生疏，希望提出一些建议，感谢！