前缀和之二维前缀和
前面讲了一维前缀和，下面我就来讲一讲二位前缀和。
1.简介
二位前缀和用于求二维数组中一个二维区间的算法，同样也是离线算法。一共分为一个步骤：二维前缀和。
2.代码
1.二维前缀和
int a[1005][1005], sum[1005][1005];
//main
int n, m, q;
cin >> n >> m >> q;
for (int i = 1; i <= n; i++){
for (int j = 1; j <= m; j++){
cin >> a[i][j];
sum[i][j] = sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];//重点：累加公式
}
}
for (int i = 1; i <= k; i++){
int x, y, z, l;
cin >> x >> y >> z >> l;
cout << sum[z][l] - sum[x-1][l] - sum[z][y-1] - sum[x-1][j-1];//重点：求区间和
cout << (z-x+1)*(l-y+1) << endl;//重点：求矩阵大小
}
这就是二维前缀和的全部了，点个赞呗。欢迎在评论区留言！
c++算法大全 文章被收录于专栏
本专栏收集了c++大部分基础算法，附有简介和代码。
投递掌阅科技等公司10个岗位
查看21道真题和解析