题解 | #【模板】二维前缀和#
【模板】二维前缀和
https://www.nowcoder.com/practice/99eb8040d116414ea3296467ce81cbbc
#include <iostream> using namespace std; const int N=1e4+10; //防止数值过大溢出 long long dp[N][N],arr[N][N]; int main() { int n,m,q; cin>>n>>m>>q; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { cin>>arr[i][j]; //在arr初始化时候顺便初始化dp if(i==j&&i==1) { dp[i][j]=arr[i][j]; } else { //公式 dp[i][j]=dp[i-1][j]+dp[i][j-1]+arr[i][j]-dp[i-1][j-1]; } } } int x1,y1,x2,y2; 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; } }