前缀和

Definition

 对于一个数组A，有另一个数组Sum，
s . t . S u m [ n ] = ∑ i = 1 n A [ i ] , n ∈ [ 1 , s i z e o f ( A ) ] , s.t.\quad Sum[n] = \sum\limits _{i=1}^n A[i] ,\quad n \in [ 1, sizeof(A)], s.t.Sum[n]=i=1∑n​A[i],n∈[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 ) O(n^2) O(n2)，在数字极大，询问次数极多时，显得有些不切实际了。

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

Application

  如前文所述， S u m [ n ] = ∑ i = 1 n A [ i ] Sum[n] = \sum\limits _{i=1}^n A[i] Sum[n]=i=1∑n​A[i]，我们可以推得：

下标	1	2	3	4	5	6	7
数组A	2	3	1	7	8	-5	9
数组Sum	2	5	6	13	21	16	25

∑ i = 3 6 A [ i ] = A [ 3 ] + A [ 4 ] + A [ 5 ] + A [ 6 ] = S u m [ 6 ] − S u m [ 2 ] \sum\limits _{i=3}^6 A[i] = A[3]+A[4]+A[5]+A[6] \\ =Sum[6] - Sum[2] i=3∑6​A[i]=A[3]+A[4]+A[5]+A[6]=Sum[6]−Sum[2]
可提炼为，对于每一次询问区间[a, b]的和：
∑ i = a b A [ i ] = S u m [ b ] − S u m [ a − 1 ] , a , b ∈ [ 1 , s i z e o f ( A ) ] \sum\limits _{i=a}^b A[i] = Sum[b] - Sum[a-1],\quad a, b\in[1, sizeof(A)] i=a∑b​A[i]=Sum[b]−Sum[a−1],a,b∈[1,sizeof(A)]
  离线的数组让每次询问的时间复杂度都是 O ( 1 ) O(1) 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^2) O(n2)优化为 O ( n ) O(n) 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

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