h95. 前缀和查询

题目描述

给定一个整数数组和若干次查询。每次查询给出一个区间 $[l,r]$，请求出该区间内所有元素的和。

输入格式

第一行输入两个整数 $n,q$，表示数组长度和查询次数。

第二行输入 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

接下来 $q$ 行，每行输入两个整数 $l,r$，表示一次查询。保证 $1\le l\le r\le n$。

输出格式

对每次查询输出一行，表示区间 $[l,r]$ 的元素和。

数据范围

• $1\le n,q\le 100000$
• $-1000\le a_i\le 1000$

样例

5 3
2 -1 4 3 5
1 3
2 5
4 4

5
11
3