计算区间和

题目描述

输入 $n$ 个整数，再输入 $m$ 个区间，每个区间的起点下标 $L$，终点下标 $R$。

对于每个区间，输出 $n$ 个整数中从下标 $L$ 到下标 $R$ 的区间和。

输入格式

第一行包括两个整数 $n$ 和 $m$。($1 \le n, m \le 500000$)

第二行包括 $n$ 个整数。($1 \le$ 整数 $\le 100$)

接下来有 $m$ 行，每行包含两个整数 $L$ 和 $R$，表示区间范围。($0 < L \le R \le n$)

输出格式

输出有 $m$ 行，每行一个整数，表示一个区间和。

样例输入 #1

10 3
2 1 3 6 4 20 15 10 4 11
3 7
1 9
5 8

样例输出 #1

48
65
49

数据范围

$1 \le n, m \le 500000$

第二行的每个整数满足 $1 \le$ 整数 $\le 100$。

对于每组区间，$0 < L \le R \le n$。

知识点与难度

本题涉及的知识点从属于 GESP 3级（一维数组、前缀和），原平台难度：Easy，难度等级：⭐⭐。

测试点分布