[C++知识库]前缀和（区间和）

前缀和

Definition

?对于一个数组A，有另一个数组Sum，
$$s.t.Sum[n]=\sum _{i=1}^{n}A[i],n\in [1,sizeof(A)],$$
我们称数组Sum为数组A的前缀和。

Let’s have an example:

区间和
给出一个长度为n的整数序列，给出m个询问。 询问的形式为[a,b]，请你快速回答第a到第b个数字之和(也就是区间a到b中所有数字之和)。
输入格式：
第一行，两个整数n和m,表示有n个整数，m个询问。
第二行，n个空格间隔的整数，表示序列中每个数字的值。
接下来m行，每行两个整数a,b，表示询问的区间。
输出格式：
m行，每行一个整数，对应一个询问的答案。
样例输入：
7 3
2 3 1 7 8 -5 9
1 3
2 6
4 7
样例输出：
6
14
19
数据范围：
1<=n<=100000
1<=m<=50000
-10000<=序列中的每个数字的值<=10000

• 方法一：暴力枚举

int n, m, Sum;
int A[100003];
int main() {
	scanf("%d%d",&n, &m);
    for(int i = 1; i <= n; ++ i)scanf("%d",&A[i]);   //将n个数字存到A数组中
    for(int i = 1; i <= m; ++ i) {          //处理m个询问
    	int x, y;
        scanf("%d%d",&x, &y);              //询问第x到第y个数之和
        Sum = 0;                           //Sum赋初值，记录x到y之和
        for(int j = x; j <= y; ++ j)Sum += A[j];
        printf("%d\n",Sum);                  //输出每次询问的结果
    }
    return 0;
}

显然这种方法最容易想到，但耗时却很长，时间复杂度达到了$O(n^2)$，在数字极大，询问次数极多时，显得有些不切实际了。

既然我们前文提到了前缀和，那么它与这样的问题有何联系呢？

Application

??如前文所述，$Sum[n]=\sum _{i=1}^{n}A[i]$，我们可以推得：

$$\begin{gathered} \sum _{i=3}^{6}A[i]=A[3]+A[4]+A[5]+A[6] \\ =Sum[6]?Sum[2] \end{gathered}$$
可提炼为，对于每一次询问区间[a, b]的和：
$$\sum _{i=a}^{b}A[i]=Sum[b]?Sum[a?1],a,b\in [1,sizeof(A)]$$
??离线的数组让每次询问的时间复杂度都是$O(1)$。
??以上展示的为一维前缀和，高维前缀和请以此类推。

• 方法二：前缀和

int n, m;
int A[100003], Sum[100003];
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++ i) {
		scanf("%d", &A[i]);
		Sum[i] = A[i] + Sum[i - 1];  //输入时初始化Sum数组
	}
	for (int i = 1; i <= m; ++ i) {
		int x, y;
		scanf("%d%d", &x, &y);
		printf("%d", Sum[y] - Sum[x - 1]);
	}
	return 0;
}

显然，这种方法牺牲空间优化时间，将在线查询离线化，大大减少了计算的时间，将时间复杂度从$O(n^2)$优化为$O(n)$，十分巧妙。

Examples

Ex.1

炸弹人
益智游戏《炸弹人》的地图是一个n*m的方格矩阵。有的方格是空地，有的方格是障碍物，有的方格里是游戏玩家们操控的“炸弹人”。
玩家可以在空地上安放炸弹，炸弹爆炸的火焰呈十字型，并可延伸到无限远出，只有遇到了障碍物才会停下来。火焰所经过的方格内如果有“炸弹人”，该“炸弹人”会被炸死，每炸死一个“炸弹人”，玩家就会获得一分。
现在你手中只剩下一颗炸弹了，你可以把这颗炸弹安放在任何空地上，问，安放在什么位置，你才能获得最大得分？
输入格式
第一行，两个空格间隔的整数n和m，表示有一个n*m的地图。
接下来是一个由整数构成的n*m的矩阵，表示当前地图的情况。其中数字0表示空地，数字1表示“炸弹人”，数字2表示障碍物。数字间以空格间隔。
输出格式
一个整数，表示最大的得分。
样例输入
5 5
0 1 0 1 2
0 1 0 0 1
1 0 1 2 1
0 1 0 0 1
0 2 1 1 0

参考代码（主要算法部分）：