文章目錄

• • 🍎1. 題目
  • 🍒2. 算法原理
  • 🍅3. 代碼實現

🍎1. 題目

題目鏈接：【模板】二維前綴和_牛客題霸_牛客網 (nowcoder.com)

描述

給你一個 n 行 m 列的矩陣 A ，下標從1開始。

接下來有 q 次查詢，每次查詢輸入 4 個參數 x1 , y1 , x2 , y2

請輸出以 (x1, y1) 為左上角 , (x2,y2) 為右下角的子矩陣的和，

輸入描述：

第一行包含三個整數n,m,q.

接下來n行，每行m個整數，代表矩陣的元素

接下來q行，每行4個整數x1, y1, x2, y2，分別代表這次查詢的參數

1 ≤ n ≤ 1000
1 ≤ q ≤ 10⁵
-10⁹ ≤ a[i] [j] ≤ 10⁹
1 ≤ x₁ ≤ x₂ ≤ n
1 ≤ y₁ ≤ y₂ ≤ m

輸出描述：

輸出q行，每行表示查詢結果。

示例1

輸入：

3 4 3
1 2 3 4
3 2 1 0
1 5 7 8
1 1 2 2
1 1 3 3
1 2 3 4

輸出：

8
25
32

備注：

讀入數據可能很大，請注意讀寫時間。

---

這題就是一個升級版的前綴和——DP34 【模板】前綴和，將一維數組升級成了二維數組

🍒2. 算法原理

解法一：暴力模擬

這里照樣直接模擬，要哪個區間到哪個區間，我們直接遍歷加上，這里時間復雜度為O(nmq)

解法二：前綴和

采用前綴和方法，分為2步：

1. 預處理出來一個前綴和矩陣，dp[i][j]表示從[1,1]位置到[i,j]位置
   
   如果我們求dp[i][j]的時候依舊從前往后依次遍歷，那這個時間復雜度也是蠻高的，我們可以將要求的dp[i][j]抽象成4個部分：
   
   那么則有dp[i][j] = A + B + C + D，其中A和D好求，B區域可以理解為(A+B)-A，C也同理(A+C)-A，這樣就能推出dp[i][j] = (A+B)+(A+C)+D-A

   所以dp[i][j] = dp[i-1][j] + dp[i][j-1] + arr[i][j] - dp[i-1][j-1]，這樣之后我們就可以直接從dp表里面拿值了，這個時間復雜度為O(1)

2. 使用前綴和矩陣，假設我們求得區域為[x₁，y₁] ~ [x₂，y₂]
   
   我們要求的就是D區域，但是dp表里面，沒有D區域的直接值，但D = (A+B+C+D) - (A+B) - (A+C) + A，表里面有A、A+B和A+C的值，所以D = dp[x2][y2] -dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1]，得出這個公式，那我們每次使用這個前綴和矩陣的時候，時間復雜度也是O(1)。

那么整體的時間復雜度為O(mn)+O(q)

🍅3. 代碼實現

#include <iostream>
#include<vector>
using namespace std;int main()
{int n = 0,m = 0,q = 0;cin>>n>>m>>q;vector<vector<int>> arr(n+1,vector<int>(m+1));for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>arr[i][j];//預處理前綴和矩陣vector<vector<long long>> dp(n+1,vector<long long>(m+1));for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)dp[i][j]=dp[i-1][j]+dp[i][j-1]+arr[i][j]-dp[i-1][j-1];//使用前綴和矩陣int x1 = 0,x2 = 0,y1 = 0, y2 = 0;while(q--){cin>>x1>>y1>>x2>>y2;    //輸入順序cout<<dp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]+dp[x1-1][y1-1]<<endl;}return 0 ;
}