#365. 【模板】前缀和 （小雷的早餐）

前缀和 （小雷的早餐）"/>

#365. 【模板】前缀和 （小雷的早餐）

【题目描述】：

小雷是个爱动的孩子。他的妈妈为了小雷能够在早餐中摄取到足够的卡路里，每天早上都把超市能买到的食物都买来了（N样食物），原样码成一排（有钱人家就是不一样）。

可是我们小雷同学为了赶时间，总是胡乱的取其中的一段食物塞进包里就出门了。他的妈妈想知道这一段食物到底含有多少卡路里？你来帮帮她快速计算这段食物的卡路里之和，当然不止一天而是M天。例如：

8 3 7 9 6 3 6 9 2 7 6 9//这是每天早上码成一排的食物中含有的卡路里

第一天：取3-7段7 9 6 3 6，总卡路里31

第二天：取5-8段6 3 6 9 ，总卡路里24

第三天：取1-4段8 3 7 9 ，总卡路里27

…

【输入描述】：

第一行两个整数N和M

第二行N个整数，表示码成一排的食物中的卡路里（每个食物的卡路里不超过100）

以下M行，每行两个整数l和r（1<=l<=r<=N），顺序表示这一天取[l,r]这一段。

【输出描述】：

对每天计算总卡路里，输出在一行。

【样例输入】：

12 3
8 3 7 9 6 3 6 9 2 7 6 9
3 7
5 8
1 4

【样例输出】：

31
24
27

【时间限制、数据范围及描述】：

时间：1s 空间：128M

1<=N<=10万; 1<=M<=50万

【解题思路】：

前缀和模板题。sum[r]-sum[l]+a[l]即为答案。

【AC代码】：

#include<bits/stdc++.h>
#define M(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
#define Mod 19650827
using namespace std;
inline void read(int &x){char ch=getchar(),c=ch;x=0;while(ch<'0' || ch>'9'){c=ch;ch=getchar();}while(ch>='0' && ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}if(c=='-')x=-x;
} int sum[100005],a[100005];
int x,i,j,l,r;
int n,m;int main(){read(n),read(m);for(i=1;i<=n;i++){read(a[i]);sum[i]=sum[i-1]+a[i];}while(m--){read(l),read(r);printf("%d\n",sum[r]-sum[l]+a[l]);}return 0;
}