一維前綴
解題思路
看到“區間之和”問題，直接想到“前綴和”
前綴和的核心公式： sum[i]=sum[i?1]+a[i]
利用前綴和求區間和 [l,r] 的公式： 區間和=sum[r]?sum[l?1]
解題步驟模板
-
輸入數組：
-
讀取數組長度 n 和查詢次數 m。
-
讀取數組 a 的每個元素。
-
-
計算前綴和：
-
初始化一個前綴和數組 sum，長度為 n+1（方便處理邊界情況）。
-
遍歷數組 a，計算前綴和
for (int i = 1; i <= n; i++) {sum[i] = sum[i - 1] + a[i]; }
-
-
處理查詢：
-
對于每個查詢 [l,r]，直接利用前綴和公式計算區間和
System.out.println(sum[r] - sum[l - 1]);
-
示例代碼模板?
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scan = new Scanner(System.in);// 輸入數組長度和查詢次數int n = scan.nextInt();int m = scan.nextInt();// 輸入數組int[] a = new int[n + 1];int[] sum = new int[n + 1];// 計算前綴和for (int i = 1; i <= n; i++) {a[i] = scan.nextInt();sum[i] = sum[i - 1] + a[i];}// 處理查詢for (int i = 0; i < m; i++) {int l = scan.nextInt();int r = scan.nextInt();System.out.println(sum[r] - sum[l - 1]);}scan.close();}
}思維導圖
-
看到“區間之和” → 想到“前綴和”
-
公式：sum[i]=sum[i?1]+a[i]
-
區間和：sum[r]?sum[l?1]
-
-
實現步驟：
-
輸入數組和查詢。
-
計算前綴和。
-
處理查詢并輸出結果。
-
訓練方法
-
遇到“區間之和”問題，直接寫前綴和公式： sum[i]=sum[i?1]+a[i] 區間和=sum[r]?sum[l?1]
-
多做類似題目，強化這種思維模式。例如：藍橋官網、力扣等平臺上的區間和問題。
二維前綴和
問題描述
給定一個?n×mn×m?大小的矩陣?AA。
給定?qq?組查詢，每次查詢為給定?44?個正整數?x1,y1,x2,y2x1?,y1?,x2?,y2?，你需要輸出?∑i=x1x2∑j=y1y2Ai,j∑i=x1?x2??∑j=y1?y2??Ai,j??的值。
輸入格式
第一行輸入?33?個正整數?n,m,qn,m,q。（1≤n,m≤103,1≤q≤1051≤n,m≤103,1≤q≤105）
接下來?nn?行每行輸入?mm?個整數，表示?Ai,jAi,j?。(?103≤Ai,j≤103,1≤i≤n,1≤j≤m)(?103≤Ai,j?≤103,1≤i≤n,1≤j≤m)
接下來?qq?行，每行輸入?44?個正整數?x1,y1,x2,y2x1?,y1?,x2?,y2?。(1≤x1≤x2≤n,1≤y1≤y2≤m)(1≤x1?≤x2?≤n,1≤y1?≤y2?≤m)
輸出格式
對于每次查詢，輸出一個整數，表示查詢的子矩陣的和。
樣例輸入
3 4 3
1 7 2 4
3 6 2 8
2 1 2 3
1 1 2 2
2 1 3 4
1 3 3 4
樣例輸出
17
27
21解題思路
1.?看到“二維區間和”問題，直接想到“二維前綴和”
-
二維前綴和的核心公式：
sum[i][j]=sum[i][j?1]+sum[i?1][j]?sum[i?1][j?1]+a[i][j] -
查詢子矩陣和的公式：
區間和=sum[x2][y2]?sum[x2][y1?1]?sum[x1?1][y2]+sum[x1?1][y1?1]
2.?實現步驟
-
輸入矩陣：
-
讀取矩陣的行數
n、列數m和查詢次數q。 -
讀取矩陣
a的每個元素。
-
-
計算二維前綴和：
-
初始化一個二維前綴和數組
sum，大小為 (n+1)×(m+1)。 -
遍歷矩陣
javaa，計算每個位置的二維前綴和：復制
for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {a[i][j] = scan.nextInt();sum[i][j] = sum[i][j - 1] + sum[i - 1][j] - sum[i - 1][j - 1] + a[i][j];} }
-
-
處理查詢：
-
對于每個查詢 (x1,y1) 到 (x2,y2)，利用二維前綴和公式計算子矩陣和：
java復制
System.out.println(sum[x2][y2] - sum[x2][y1 - 1] - sum[x1 - 1][y2] + sum[x1 - 1][y1 - 1]);
-
-
輸出結果：
-
對每個查詢輸出對應的子矩陣和。
-
?代碼模板
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scan = new Scanner(System.in);// 輸入矩陣的行數、列數和查詢次數int n = scan.nextInt();int m = scan.nextInt();int q = scan.nextInt();// 創建數組存儲原始矩陣和前綴和int[][] a = new int[n + 1][m + 1];int[][] sum = new int[n + 1][m + 1];// 計算二維前綴和for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {a[i][j] = scan.nextInt();sum[i][j] = sum[i][j - 1] + sum[i - 1][j] - sum[i - 1][j - 1] + a[i][j];}}// 處理查詢for (int i = 0; i < q; i++) {int x1 = scan.nextInt();int y1 = scan.nextInt();int x2 = scan.nextInt();int y2 = scan.nextInt();System.out.println(sum[x2][y2] - sum[x2][y1 - 1] - sum[x1 - 1][y2] + sum[x1 - 1][y1 - 1]);}scan.close();}
}總結
-
看到“二維區間和”問題，直接想到“二維前綴和”。
-
核心公式：
-
二維前綴和：sum[i][j]=sum[i][j?1]+sum[i?1][j]?sum[i?1][j?1]+a[i][j]
-
查詢子矩陣和：區間和=sum[x2][y2]?sum[x2][y1?1]?sum[x1?1][y2]+sum[x1?1][y1?1]
-
-
實現步驟：
-
輸入矩陣和查詢。
-
計算二維前綴和。
-
處理查詢并輸出結果。
-
相關的習題練習
小秋的矩陣
問題描述
給你一個?nn?行?mm?列只包含?00?和?11?的矩陣，求它的所有子矩陣中，是方陣而且恰好包含?kk?個?00?的數量。
方陣是行數和列數相等的矩陣。
子矩陣是從一個矩陣當中選取某些行和某些列交叉位置所組成的新矩陣（保持行與列的相對順序），被稱為原矩陣的一個子矩陣。
輸入格式
第?11?行輸入?33?個整數?n,m,kn,m,k，表示矩陣的行數，列數和所求子矩陣包含?00?的數量。
接下來?nn?行，每行輸入?mm?個整數，第?ii?表示給定矩陣的第?ii?行。
輸出格式
輸出僅一行，包含?11?個整數，表示答案。
樣例輸入
3 4 2
0 1 1 0
1 0 0 1
0 1 0 0
樣例輸出
4
說明
共有?44?個階數為?22?的方陣符合條件，左上角的坐標分別為?(1,1),(1,2),(1,3),(2,1)(1,1),(1,2),(1,3),(2,1)。
評測數據規模
對于?2020% 的評測數據，1≤n×m≤1031≤n×m≤103。
對于?4040% 的評測數據，1≤n×m≤1051≤n×m≤105。
對于?100100% 的評測數據，1≤n×m≤1061≤n×m≤106，0≤k≤n×m0≤k≤n×m。
代碼實現
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scan = new Scanner(System.in);// 讀取行數、列數和目標零的個數int n = scan.nextInt();int m = scan.nextInt();int k = scan.nextInt();// 創建數組存儲原始矩陣和前綴和int[][] tur = new int[n + 1][m + 1];int[][] sum = new int[n + 1][m + 1];// 輸入矩陣并計算前綴和for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {tur[i][j] = scan.nextInt();sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + tur[i][j];}}// 計數符合條件的子矩陣int count = 0;// 遍歷所有可能的正方形子矩陣的大小for (int size = 1; size <= Math.min(n, m); size++) {// 遍歷所有可能的起始位置for (int i = 1; i <= n - size + 1; i++) {for (int j = 1; j <= m - size + 1; j++) {// 計算子矩陣的右下角坐標int x2 = i + size - 1;int y2 = j + size - 1;// 計算子矩陣的和int total = sum[x2][y2] - sum[x2][j - 1] - sum[i - 1][y2] + sum[i - 1][j - 1];// 計算子矩陣中零的個數int tmp = size * size - total;// 如果符合條件，計數器加1if (tmp == k) {count++;}}}}// 輸出結果System.out.println(count);scan.close();}
}?自學藍橋杯筆記,希望我們可以一起學習!
)
