#O1026. 区间求和

区间求和

题目描述

给定长度为 nn 的整数序列 a1,a2,…,ana_1, a_2, \ldots, a_n,回答 qq 次询问,每次给出 l,rl, r,求 ∑i=lrai\sum\limits_{i=l}^{r} a_i。

题目类型

前缀和

输入格式

第一行两个整数 n,qn, q。

第二行 nn 个整数。

接下来 qq 行,每行两个整数 l,rl, r。

输出格式

共 qq 行,每行一个整数表示对应询问的答案。

样例 #1

样例输入 #1

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

样例输出 #1

15
5
4

数据规模与约定

数据范围 说明
1≤n,q≤2×1051 \le n, q \le 2 \times 10^5 序列长度与询问次数
−109≤ai≤109-10^9 \le a_i \le 10^9 元素范围
1≤l≤r≤n1 \le l \le r \le n 询问区间
  • 前缀和需用 long long。