前綴和

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]，我們可以推得：

∑ 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

參考代碼（主要演算法部分）：