静态区间和查询 (Static Range Sum Queries)

题目描述

给定一个包含 n 个整数的数组，你的任务是处理 q 个查询。每个查询的形式为：数组中从位置 a 到 b 的所有数值之和是多少？

输入格式

• 第一行包含两个整数 n 和 q：分别表示数组元素的数量和查询的数量。
• 第二行包含 n 个整数 x1, x2, ..., xn：表示数组中的具体数值。
• 接下来有 q 行，每行包含两个整数 a 和 b：表示查询区间 [a, b] 的起止位置（下标从 1 开始）。

输出格式

对于每个查询，输出对应的区间和，每个结果占一行。

数据范围

• 1 <= n, q <= 2 * 10^5
• 1 <= xi <= 10^9
• 1 <= a <= b <= n

样例输入

Plaintext

8 4
3 2 4 5 1 1 5 3
2 4
5 6
1 8
3 3

样例输出

Plaintext

11
2
24
4

解题核心提示

1. ​前缀和数组​：创建一个新数组 S，其中 S[i] = x1 + x2 + ... + xi。
2. ​计算公式​：区间 [a, b] 的和 = S[b] - S[a-1]。
3. ​数据类型​：由于累加和可能非常大（最大约 2 * 10^14），在 C++ 中必须使用 long long，在 Java 中使用 long。