P1004 flying的刷题记录

一.解题思路

1.碎碎念

背景竟然是我！虽然但是俺备战🏀杯刷的那几道题其实一只手就能数过来（雾

所以 理论上来讲，暴力完全应该能做，但显然社长认为俺很勤奋，竟然能刷这么多！

2.题目详解

其实就是给你一串数字，然后问你每一段的和，数据量小的话直接上手数比写代码快，但如果比较大的话，那就不得不掏出我们的神器——— 前缀和 了！

3.算法实现

核心代码：pre[i] = pre[i-1] + num[i]; 这一串就是前缀和的核心了，字面意思，假设给你一串数字

1 1 4 5 1 4

那么**pre[1]到pre[6]**就是

1 2 6 11 12 16

pre[2]就是pre[1]加上num[2]

这样做在计算区间和时就不用面对可恶的TLE了

比如，还是刚拿一串114514，L=2，R=6的话，直接数ans=1+4+5+1+4 = 15

前缀和的话就是pre[R]-pre[L-1] = 16-1 = 15

省去了大量复杂重复的计算，简直就是（最）伟大的算法（之一）！

4.复杂度

1.时间：O(n+q)

2.空间：O(n)

二.完整代码

PS：非专业题解！有任何错误记得联系我！！！

C语言 #include<stdio.h>

#define MAX_N 100005

long long prefix[MAX_N];

int main() { int n,q; scanf("%d %d",&n,&q);

prefix[0]=0;

for(int i=1;i<=n;i++)
{
    int val;
    scanf("%d",&val);
    prefix[i]=prefix[i-1]+val;
}
while(q--)
{
    int L,R;
    scanf("%d %d",&L,&R);

    printf("%lld\n",prefix[R]-prefix[L-1]);
}

return 0;

}