2461. 计算区间和
1000ms
256MB
简单
前缀和与差分
题目描述
输入 $n$ 个整数，再输入 $m$ 个区间。每个区间由起点下标 $L$ 和终点下标 $R$ 组成。
请对于每个区间，输出原数组中从下标 $L$ 到下标 $R$ 的所有元素之和。
输入格式
- 第一行包含两个整数 $n$ 和 $m$ ($1 \le n, m \le 500,000$)。
- 第二行包含 $n$ 个整数 ($1 \le \text{整数} \le 100$)。
- 接下来 $m$ 行，每行包含两个整数 $L$ 和 $R$，表示区间范围 ($1 \le L \le R \le n$)。
输出格式
- 输出共 $m$ 行，每行一个整数，表示对应区间的和。
样例 1
输入 (Input)
输出 (Output)
- $n, m \le 500,000$。
- 必须使用**前缀和**算法，否则 $O(n \cdot m)$ 的暴力枚举会导致超时。
- 建议使用快速输入输出手段。
› 输入 stdin
CtrlShiftEnter
‹ 输出 stdout
错误 stderr
操作成功