SSOJ2612区间求和
2479+
作者：crxis 发布：2017-11-23 分类：前缀和
题目大意：给你n个整数，请问第x个到第y个的和是多少？
输入
第一行2个正整数n、m
接下来1行n个整数
接下来m行，每行两个整型x、y
输出
输出m行，每一行都代表一个区间的和
样例输入
5 2
1 2 -3 6 5
2 4
1 3
样例输出
5
0
提示
1<=x、y<=n；n个数，每个数的绝对值不超过1000；5<=n、m<=200000
(10个点数据范围：5, 10, 100, 500, 1000, 5000, 10000, 50000, 100000, 150000, 200000)
解题思路
读入n个数，对于每次循环，累加a[x]、a[x+1]、…、a[y]，时间复杂度是O(n^2)。如何做到O(n)呢？我们可以定义一个数组s，让s[i]表示前i个的和，这样求x到y这个区间的和，只需要用前y个的和s[y]减去前x-1个的和s[x-1]即可。前缀和可以用递推求得，前i个的和等于钱i-1个的和加上第i个数：s[i] = s[i-1] + a[i]。
程序实现
暴力70分：
