#P1518. 区间和

    ID: 24 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>一维数组赛制:OI来源:wyfoj http://127.0.0.1前缀和递推

区间和

区间和

题目描述

输入一个长度为n(1 <= n <= 1000)的数组a,元素为a[1]....a[n],之后进行m次询问,每次询问给出两个值(l,r)(r >= l),求数组:a[i] + a[i+1] + ..... a[j]的值。

例如:n = 3,m = 3,a的元素为1, 3, 5,

第1个查询为:1 2,对应a[1] + a[2] = 1 + 3 = 4

第2个查询为:1 3,对应a[1] + a[2] + a[3] = 1 + 3 + 5 = 9

第3个查询为:2 3,对应a[2] + a[3] = 3 + 5 = 8

输入格式

第一行2个数,n和m,中间用空格分隔(50%的数据1 <= n, m <= 1000,100%的数据1 <= n, m <= 100000)。 之后n+m行,

第 1 至 n 行:每行一个数字a[i](0 <= a[i] <= 1000)

第 n + 1 至 n + m 行:每行2个数字l,r,中间用空格分隔(0 < l <= r <= n)

输出格式

输出共m行,每行一个数,对应a[i] + a[i+1] + ..... a[j]的值。

数据范围

(原站未提供,导入后需人工补齐)

样例

3 3
1
3
5
1 2
1 3
2 3
4
9
8