给定一个长度为 n 的数组 a1、a2、……、an。接下来有 q 次查询, 每次查询有两个参数 left、right。
对于每个询问, 请输出
输入描述：
第一行包含两个整数 n 和 q。
第二行包含 n 个整数，表示 a1、a2、……、an。
接下来 q 行，每行包含两个整数 left 和 right。
其中数据范围为：
输出描述：
输出 q 行，每行代表一次查询的结果。
示例1：
输入：
3 2
1 2 4
1 2
2 3
输出：
3
6解题思路：前缀和
暴力解法这里就不说了，比较简单，就是一个普通的枚举，但是这种暴力解法的问题就是时间复杂度比较高，我们需要每次去查询的时候，需要从头开始计算区间的和，这是非常耗时的！
我们先想哈，之所以暴力破解时间复杂度高，其实就是因为每次我们都得从头去计算某个区间的元素和，这是非常麻烦的，但是我们发现一个规律，既然我们要求一个的是一个区间的元素和，实际上是可以用减法来得到的，如下图所示：
也就是说，我们可以这道题就转化为了求 [0, left-1] 和 [0, right] 区间的元素和，而又因为这段区间其实重复元素是很多的，我们可以用一个数组来记录下这些会发生重复的元素，而不用我们每次都去重新计算元素和，其实就是前缀和的思想！
与其说是前缀和，其实不如说是简单的动态规划！
假设 dp[i] 表示从 [0, i] 位置处的总和，那么很容易就能得到状态转移方程 dp[i] = dp[i - 1] + arr[i]。（这里就不解释了，之前写过挺多动态规划的题了！）
因为用到了 i-1 处下标，所以这里我们可以开辟虚拟位置，实际位置从 1 开始遍历！
最后我们就能求出一个总和数组，如下所示：
那么此时我们就能在 O(1) 的时间复杂度中得到 [0, right] 和 [0, left-1] 区间的元素和！
这就是前缀和，怎么样，其实很简单吧，就是一个动态规划问题！
#include <iostream>
#include <vector>
using namespace std;
int main()
{
// 输入信息
int n, q;
cin >> n >> q;
vector<int> arr(n + 1);
for(int i = 1; i <= n; ++i)
cin >> arr[i];
// 前缀和处理
vector<long long> prefix(n + 1); // 注意这里是需要用long long的，不然用int会溢出
for(int i = 1; i <= n; ++i)
prefix[i] = prefix[i - 1] + arr[i];
while(q--)
{
int left, right;
cin >> left >> right;
cout << prefix[right] - prefix[left - 1] << endl; // 两个区间相减之后得到中间的区间
}
return 0;
}