csl不小气

发布时间: 2017年6月24日 14:10   最后更新: 2017年6月24日 14:13   时间限制: 1000ms   内存限制: 128M

csl可开心,又碰到一个签到题,但是他不是一个小气的人,他把这个签到题和你分享了一波,他是多么的慷慨啊。给你一个长度为$n$的数列,之后有$q$次查询,每次查询给出两个正整数 $l,r$。你需要求出下标从$l$到$r$之间的所有数字之和。

多组输入,第一行输入一个正整数$n,(n< 10^5)$表示数列的长度和$q,(q < 10^6)$,表示查询次数。
第二行有$n$个数$x_1,x_2,x_3,...,x_n$,$( - 10^4 < x_i < 10^4 )$。
接下来$q$行每行两个数字 $l,r$。$l \le r \le n$。

对于每个查询输出一个正整数,表示闭区间$[l,r]$的和。

复制
5 2
1 2 3 4 5
1 2
2 3
3
5

直接暴力做会超时的哦~

Source: OneDay

data structure

16级第一次周末赛