#P90. 数组求和(大数据版)

数组求和(大数据版)

题目描述

前缀和的技巧,必须要建立和熟练运用,这道题就是前缀和的基础应用。

陶陶学了数组以后,他对数组之间的累加和特别感兴趣,于是他就提出了要求 数组 元素之间的累加和的问题。

例如:现在有长度为 10 的数组: 3 2 5 1 4 5 3 7 8 2

从第2个元素到 第 5个元素的和就是 2+5+1+4=12

从第4个元素到第9个元素的和就是 1+4+5+3+7+8=28

输入格式

第一行 n k 两个正整数,分别表示 数组有n个元素,k次求和查询 (0<=n,k<=100000)

第二行为n个整数 数组的n个元素

以下有k行,每行两个元素,为求和的起点和终点

输出格式

k行,每行为起点到终点的和.

样例

input

10 2
3 2 5 1 4 5 3 7 8 2
2 5
4 9

output

12
28

限制与提示

时间限制:1s1 \text {s}

空间限制:256MB256 \text {MB}