前缀和-一维

输入一个长度为 n 的整数序列。

接下来再输入 m个询问，每个询问输入一对 l,r。

对于每个询问，输出原序列中从第 l 个数到第 r 个数的和。

第一步

首先做一个预处理，定义一个sum[]数组，sum[i]代表a数组中前i个数的和。

第二步

求前缀和运算：

int sum[N],a[N]; //sum[i]=a[1]+a[2]+a[3].....a[i];
for(int i=1;i<=n;i++)
{ 
    sum[i]=sum[i-1]+a[i];   
}

第三步

然后查询 *** 作：

 scanf("%d%d",&l,&r);
 printf("%dn", sum[r]-sum[l-1]);

图解

 完全代码

#include 
using namespace std;
const int N=100010;
int q[N],sum[N];
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>q[i];
        sum[i]+=sum[i-1]+q[i];
    }
    while(m--)
    {
        int l,r;
        cin>>l>>r;
        cout< 
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5670780.html