前缀和处理数组区间之和问题
1.什么是区间和问题
“区间和问题”通常指的是涉及计算或处理数组或数列某个子区间（即一段连续元素）的总和的类型问题。这类问题可能有多种变体和不同的复杂度，但基本思想都是在给定的区间内快速计算总和或处理与区间和相关的操作。
2.例题
题目描述
给定一个整数数组 Array，请计算该数组在每个指定区间内元素的总和。
输入描述
第一行输入为整数数组 Array 的长度 n，接下来 n 行，每行一个整数，表示数组的元素。随后的输入为需要计算总和的区间下标：a，b （b > = a），直至文件结束。
输出描述
输出每个指定区间内元素的总和。
3.解题思路
在看到题目的第一反应，大多数同学认为这是一道非常简单的数组求和问题，只需要将区间中对应下标的元素依次相加即可，但通过这种方法提交问题往往会编译超时。why？取极端情况：如果我次次查询的范围都是n-1到0，那么算法的复杂度是O(n * m) m，也就是查询的次数。可见查询次数非常多，而且时间也很长。
所以，为了加速区间和的查询，可以创建一个前缀和数组。前缀和数组 P[i] 表示原数组 A 从第1个元素到第 i 个元素的和。利用前缀和数组可以在 O(1) 时间内计算任意区间的和：
通过上面的图示可以看出，Sum(a,b)=P[b]−P[a−1]
注意这里a不可以为0，a为0要单独考虑:Sum(0,b)=P[b]
计算前缀和数组的时间复杂度是 O(n)，每个查询时间复杂度是 O(1)。
有了前缀和数组之后，我们就可以在输入原数组元素时，设定一个累加变量，输入一次累加变量就增加一次。而前缀和数组的每个元素大小就是对应的累加变量的大小。
代码如下：
# include <iostream>
# include <vector>
using namespace std;
int main(){int n,a,b;scanf("%d",&n);vector<int> vec(n);vector<int> p(n);int presum=0;for(int i=0;i < n;i++){scanf("%d",&vec[i]);presum+=vec[i];p[i]=presum;}while(~scanf("%d%d", &a, &b)){int sum;if(a==0) sum=p[b];else sum = p[b]-p[a-1];printf("%d\n",sum);}
}
4.小节
1.scanf 函数返回成功读取的输入项的数量（如成功读取两个整数则返回 2），如果遇到输入错误或到达文件末尾，scanf 会返回 EOF（通常为 -1）。while (~scanf("%d%d", &a, &b)) 这行代码的意思是对 scanf 的返回值进行按位取反，然后将结果用于 while 循环的条件判断。
2.当对 scanf 的返回值使用 ~ 时，如果 scanf 成功读取了输入项，返回值将不为 0，而取反后的结果通常为一个负数；如果 scanf 返回 -1（即 EOF），则 ~(-1) 将得到 0，这时循环会停止。
3.C++ 代码中面对大量数据的读取、输出操作时，最好用scanf 和 printf，而不是cin和cout。因为scanf和printf耗时会小很多
4.区间和问题是许多编程竞赛和算法面试中常见的题型，掌握这些问题的高效解法对提升算法和数据结构的能力非常重要。