a694 - 吞食天地二
題目描述
題目要求計算一個 n x n 的矩陣中，給定區塊 (x1, y1) 到 (x2, y2) 的所有元素的總和。輸入包含多組測試案例，每組案例包含矩陣的大小 n 和查詢次數 m，以及矩陣元素和查詢座標。
解題思路
本題的核心思想是使用前綴和 (Prefix Sum) 技術來高效地計算矩陣區塊的和。首先，我們建立一個前綴和矩陣 sum，其中 sum[i][j] 儲存了原始矩陣中 (1, 1) 到 (i, j) 的所有元素的總和。
計算前綴和矩陣的公式如下：
sum[i][j] = sum[i][j-1] + sum[i-1][j] - sum[i-1][j-1] + matrix[i][j]
有了前綴和矩陣，我們就可以在 O(1) 的時間內計算任何子矩陣的和。給定一個區塊 (x1, y1) 到 (x2, y2)，其總和可以通過以下公式計算：
total = sum[x2][y2] - sum[x2][y1-1] - sum[x1-1][y2] + sum[x1-1][y1-1]
複雜度分析
- 時間複雜度: O(n^2 + m)
- 建立前綴和矩陣需要 O(n^2) 的時間。
- 處理 m 個查詢，每個查詢需要 O(1) 的時間，總共需要 O(m) 的時間。
- 空間複雜度: O(n^2)
- 需要額外 O(n^2) 的空間來儲存前綴和矩陣。
程式碼
#include <stdio.h>
int main() {
int n,m,x1,y1,x2,y2,i,j,temp,total;
while(scanf("%d%d",&n,&m)!=EOF){
int sum[n+1][n+1];
for(i=0;i<=n;i++){
sum[0][i]=0;
sum[i][0]=0;
}
for(i=1;i<=n;i++)
scanf("%d",&temp),sum[1][i]=sum[1][i-1]+temp;
for(i=2;i<=n;i++){
for(j=1;j<=n;j++){
scanf("%d",&temp);
sum[i][j]=sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1]+temp;
}
}
for(i=0;i<m;i++){
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
total=sum[x2][y2]-sum[x2][y1-1]-sum[x1-1][y2]+sum[x1-1][y1-1];
printf("%d\n",total);
}
}
}