前缀和之二维前缀和

前面讲了一维前缀和，下面我就来讲一讲二位前缀和。

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;//重点：求矩阵大小
}

这就是二维前缀和的全部了，点个赞呗。欢迎在评论区留言！