在學習本篇內容前建議先學習一下“一維前綴和”

一維前綴和 算法https://blog.csdn.net/czt230610/article/details/148012923?fromshare=blogdetail&sharetype=blogdetail&sharerId=148012923&sharerefer=PC&sharesource=czt230610&sharefrom=from_link接下來我們就直接從題引入

如果一維的話，很容易想到創建“前綴和”數組進行相減，但到了二維，我們要在每一行、每一列都要創建一個“前綴和”數組嗎？顯然太麻煩了，我們用一下數學思維或許使這個問題更加簡單化。所以本題的暴力解我們就不多說了。

根據我們的算法原理：創建前綴和數組并使用，我們要“更便利“地創建這個數組。

首先，這個數組的含義是不能變的，dp[i][j]記錄的是從[1，1]到dp[i，j]的所有和（為什么下標從1開始在一維模板中有說明）,現在我們求dp[i][j]

根據題意，就是把圖中arr的ABCD中所有元素求和即可（D就是arr[i][j]），如果我們直接求A+B+C+D，發現還是很麻煩，我們可以采用，(A+C)+(A+B)+D-A的方式，換成代碼就是dp[i][j-1]+dp[i-1][j]+arr[i][j]-dp[i-1][j-1]，這就是前綴和數組的預處理。

接下來是使用

上圖是arr數組，我們要求出[x1,y1]-[x2,y2]之間的和（圖中的D），我們可以用A+B+C+D-(A+B)-(A+C)+A.即dp[x2,y2]-dp[x1-1,y2]-dp[x2,y1-1]+dp[x1-1,y1-1]。這里的坐標-1用一下3×3表格模擬即可得出原因。

現在我們可以寫題解（模板）了

#include <iostream>using namespace std;
#include <vector>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]-dp[i-1][j-1]+arr[i][j];//使用int x1=0=,y1=0,x2=0,y2=0;while(q--){cin >>x1>>y1>>x2>>y2;cout<<dp[x2][y2]-dp[x2,y1-1]-dp[x1-1,y2]+dp[x1-1,y1-1]<<endl;}return 0;
}