区间和

课程自编 · 一维前缀和

题目描述

给出一个长度为 $n$ 的整数序列 $a_1,a_2,\dots,a_n$。有 $q$ 次询问，每次询问给出两个整数 $l,r$，请输出 $a_l+a_{l+1}+\cdots+a_r.$

输入格式

第一行两个整数 $n,q$。第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$。接下来 $q$ 行，每行两个整数 $l,r$。

输出格式

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

数据范围与约定

$1 \le n,q \le 2\times 10^5$，$|a_i| \le 10^9$，$1 \le l \le r \le n$。

样例输入

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

样例输出

6
14
4

样例说明

区间 $[2,4]$ 的和为 $1+4+1=6$；整个序列的和为 $14$；$[3,3]$ 的和为 $4$。使用前缀和 $s_i=s_{i-1}+a_i$，答案为 $s_r-s_{l-1}$。

说明

课程自编题，数据由 src/gen.py 生成。