18927 前缀和

18927 前缀和

Description

前缀和是一种重要的预处理方法,能极大地降低查询序列区间和的时间复杂度。
现在一个序列中有n个整数,下标从1....n。
有m个查询,每个查询给出一个区间的左右端点下标,请输出这个区间所有数据的和。

输入格式

第一行一个整数n。(1<=n<=100000)
第二行n个整数,用空格分隔,int范围。
第三行一个整数m。(1<=m<=100000)
下面m行每行两个整数L,R。(1<=L<=R<=n)

输出格式

输出共m行,每行一个整数为对应区间[L,R]的序列和。
注意序列和的数据范围可能超出int范围。

输入样例

5
3 -8 4 5 1 
4
3 3
1 1
2 4
1 3

输出样例

4
3
1
-1

提示

在读入数据后,用一个sum数组来记录从第1个元素到第i个元素的和,for(i=1;i<=n;i++) sum[i]=sum[i-1]+a[i];
这样区间[L,R]的和可以用sum[R]-sum[L-1]得到。

作者 30002692

#include<stdio.h>
int main()
{
    int n;
    scanf("%d",&n);
    long long a[n+1];
    a[0]=0;
    int i;
    int input;
    for(i=0;i<n;i++)
    {
        scanf("%d",&input);
        a[i+1]=a[i]+input;
    }
    int L,R;
    scanf("%d",&n);
    while(n--)
    {
        scanf("%d%d",&L,&R);
        printf("%lld\n",a[R]-a[L-1]);
    }
}

Mark

输出范围会大于int的取值范围,需要用lld输出

版权声明:本文为 溪月阁 | MoBrook 博主「 皓月 」的原创文章遵循用 CC BY-NC-SA 4.0 版权协议进行许可,转载请附上原文出处链接及本声明。

本文链接https://mobrook.cn/index.php/scau-18927/

没有了,已经是最后文章

下一篇: