#O1026. 区间求和
区间求和
题目描述
给定长度为 的整数序列 ,回答 次询问,每次给出 ,求 。
题目类型
前缀和
输入格式
第一行两个整数 。
第二行 个整数。
接下来 行,每行两个整数 。
输出格式
共 行,每行一个整数表示对应询问的答案。
样例 #1
样例输入 #1
5 3
1 2 3 4 5
1 5
2 3
4 4
样例输出 #1
15
5
4
数据规模与约定
| 数据范围 | 说明 |
|---|---|
| 序列长度与询问次数 | |
| 元素范围 | |
| 询问区间 |
- 前缀和需用
long long。
给定长度为 n 的整数序列 a1,a2,…,an,回答 q 次询问,每次给出 l,r,求 i=l∑rai。
前缀和
第一行两个整数 n,q。
第二行 n 个整数。
接下来 q 行,每行两个整数 l,r。
共 q 行,每行一个整数表示对应询问的答案。
5 3
1 2 3 4 5
1 5
2 3
4 4
15
5
4
| 数据范围 | 说明 |
|---|---|
| 1≤n,q≤2×105 | 序列长度与询问次数 |
| −109≤ai≤109 | 元素范围 |
| 1≤l≤r≤n | 询问区间 |
long long。