[SDOI2016小学组] 数苹果（apple）

题目描述

苹果丰收了，有 n 堆苹果，小红就在苹果堆旁。小红已经知道了每堆苹果有多少个。 她要问一问从第 a 堆到第 b 堆一共有多少个苹果。

输入

输入数字 n，然后输入 n 个数据。再输入问 m，然后输入 c 行数据。

输出

输出 m 次 a 到 b 堆一共有多少个。

样例输入 复制

5
1 2 3 4 5
3
1 3
2 4
1 5

样例输出 复制

6
9
15

提示

【数据范围】 对于80% 的数据：0≤n≤10000； 对于100% 的数据：0≤n≤100000。

这不是前缀和吗，给大家看一下错误代码：

#include<iostream>
using namespace std;
int main()
{
    int x;
    cin>>x;
    int a[x+1];
    for (int i = 0; i < x; i++) {
        cin>>a[i];
    }
    int n;
    cin>>n;
    int n1,n2;
    for (int i = 0; i < n; i++) {
        cin>>n1>>n2;
        int x = 0;
        for (int i = n1-1; i < n2; i++) {
            x+=a[i];
        }
        cout<<x<<endl;
    }
    return 0;
}

成功的时间超限了；加上下面的加速也不行

ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);

所以，只能用前缀和

AC代码： 

#include<iostream>
using namespace std;
int main()
{   
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int x;
    cin>>x;
    int a[x+1],b[x+1] = {0};
    for (int i = 1; i <= x; i++) {
        cin>>a[i];
        b[i] = b[i-1]+a[i];
    }
    int n;
    cin>>n;
    int n1,n2;
    for (int i = 0; i < n; i++) {
        cin>>n1>>n2;
        cout<<b[n2] - b[n1-1]<<"\n";
    }
    return 0;
}