基础算法|线性结构|前缀和学习

 参考文章：

https://blog.csdn.net/weixin_72060925/article/details/127835303

二维数组的前缀和练习：

这里要注意的地方就是求子矩阵和的时候，这里要减去的是x1-1，y1-1的部分，因为所求的目标值是包括边界的

//前缀和基础练习 #include<bits/stdc++.h>
#define int long long
using namespace std; 
const int N=5*1e3+10;
int n,m,q;
int nums[N][N]={0};
int s[N][N]={0};
signed main() {scanf("%d %d %d",&n,&m,&q);for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){scanf("%d",&nums[i][j]);s[i][j]=s[i][j-1]+s[i-1][j]+nums[i][j]-s[i-1][j-1];}}while(q--){int x1,y1,x2,y2;scanf("%d %d %d %d",&x1,&y1,&x2,&y2);int ans=0;//注意这里要减去的是x1-1，y1-1的部分，因为所求的目标值是包括边界的 ans=s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1];cout<<ans<<endl;}return 0;
}

测试： 

/*
输入： 
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*/