前綴和矩陣（Prefix Sum Matrix）是一種預處理技術，用于快速計算二維矩陣中任意子矩陣的元素和。其核心思想是通過提前計算并存儲每個位置左上角所有元素的和，將子矩陣和的查詢時間從暴力計算的 (O(mn)) 優化到 (O(1))。以下是構建前綴和矩陣的詳細步驟和示例：

---

1. 定義原矩陣與前綴和矩陣

• 原矩陣：一個 m X n 的二維數組 matrix，元素為整數或浮點數。
• 前綴和矩陣：一個與 matrix 同尺寸的二維數組 prefix，其中 prefix[i][j] 表示從左上角 (0,0) 到 (i,j) 形成的子矩陣所有元素之和。

---

2. 構建前綴和矩陣的步驟

步驟 1：初始化前綴和矩陣

• 創建一個與原矩陣大小相同的二維數組 prefix。
• 通常將 prefix 的索引從 (0,0) 開始（與 matrix 對齊）。

步驟 2：遞推公式

• 邊界條件：

  • 當 i=0 且 j=0 時：

    							prefix[0][0] = matrix[0][0]
    

  • 當 i=0 時（第一行）：

    					prefix[0][j] = prefix[0][j-1] + matrix[0][j]
    

  • 當 j=0 時（第一列）：

    					prefix[i][0] = prefix[i-1][0] + matrix[i][0]
    

• 一般情況（i>0 且 j>0）：

  				prefix[i][j] = matrix[i][j] + prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1]
  

  解釋：
  當前元素的值 matrix[i][j]，加上上方子矩陣的和 prefix[i-1][j]，加上左方子矩陣的和 prefix[i][j-1]，再減去重復計算的左上角子矩陣 prefix[i-1][j-1]。

---

3. 構建示例

假設原矩陣 matrix 如下：

                                           [1  2  3][4  5  6][7  8  9]

逐行構建前綴和矩陣 prefix：

1. 初始化 prefix[0][0]：

   							prefix[0][0] = matrix[0][0] = 1
   

2. 第一行（i=0）：

   					prefix[0][1] &= prefix[0][0] + matrix[0][1] = 1 + 2 = 3 prefix[0][2] &= prefix[0][1] + matrix[0][2] = 3 + 3 = 6 
   

3. 第一列（j=0）：

   					prefix[1][0] &= prefix[0][0] + matrix[1][0] = 1 + 4 = 5 prefix[2][0] &= prefix[1][0] + matrix[2][0] = 5 + 7 = 12 
   

4. 一般位置（i>0 且 j>0）：

   • prefix[1][1]：

     								5 + 5 + 3 - 1 = 12
     

   • prefix[1][2]：

     								6 + 12 + 6 - 3 = 21
     

   • prefix[2][1]：

     								8 + 12 + 12 - 5 = 27
     

   • prefix[2][2]：

     								9 + 27 + 21 - 12 = 45
     

最終前綴和矩陣：

                                            [1  3   6 ][5  12  21][12 27  45]

---

4. 查詢子矩陣和

構建前綴和矩陣后，計算子矩陣 (x1, y1) 到 (x2, y2) 的和公式為：

	Sum = prefix[x2][y2] - prefix[x1-1][y2] - prefix[x2][y1-1] + prefix[x1-1][y1-1]

示例：
計算子矩陣 (1,1) 到 (2,2)（即原矩陣中的 5,6,8,9）的和：

	Sum = 45 - 6 - 12 + 1 = 28

---

5. 代碼實現（C++）

#include <vector>
using namespace std;vector<vector<int>> buildPrefixSum(vector<vector<int>>& matrix) {int m = matrix.size(), n = matrix[0].size();vector<vector<int>> prefix(m, vector<int>(n, 0));// 初始化第一行和第一列prefix[0][0] = matrix[0][0];for (int j = 1; j < n; j++) prefix[0][j] = prefix[0][j-1] + matrix[0][j];for (int i = 1; i < m; i++) prefix[i][0] = prefix[i-1][0] + matrix[i][0];// 填充其他位置for (int i = 1; i < m; i++) {for (int j = 1; j < n; j++) {prefix[i][j] = matrix[i][j] + prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1];}}return prefix;
}

---

關鍵點總結

• 時間復雜度：構建前綴和矩陣需 (O(mn))，查詢子矩陣和僅需 (O(1))。
• 適用場景：頻繁查詢子矩陣和的場景（如動態規劃、圖像處理）。
• 邊界處理：注意索引從 0 開始，避免越界訪問。