241982 - 连续区间求和

题目描述

给定一个长度为 n 的正整数序列 a_1,a_2,\ldots,a_n。

现在需要回答 q 次询问,每次给定两个整数 l,r,求下标从 l 到 r 的所有元素之和。

即:

S(l,r)=\sum_{i=l}^{r}a_i

输入

第一行输入两个整数 n,q,分别表示序列长度和询问次数。

第二行输入 n 个正整数,表示序列中的元素。

接下来 q 行,每行输入两个整数 l,r,表示需要求和的区间。

输出

输出 q 行,每行一个整数,表示对应区间的元素之和。

样例

输入

5 3
100 200 300 400 500
1 3
2 5
1 5

输出

600
1400
1500
说明

样例解释

第一次询问:

100+200+300=600

第二次询问:

200+300+400+500=1400

第三次询问:

100+200+300+400+500=1500

数据范围

对于全部测试数据,保证:

  • 1 \le n,q \le 10^5
  • 1 \le a_i \le 10^9
  • 1 \le l \le r \le n
标签
题目参数
时间限制 1 秒
内存限制 256 MB
提交次数 5
通过人数 1
金币数量 3 枚
难度 基础


上一题 下一题