题解 | #【模板】二维前缀和#

#include<iostream>
using namespace std;
#include<vector>

//1.预处理出来一个前缀和矩阵dp
//dp[i][j]表示从(1,1)位置到(i,j)位置，这段区间中所有元素的和

int main()
{
	int n = 0, m = 0;//n行m列
	cin >> n >> m;
	int q = 0;//查询次数
	cin >> 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] + arr[i][j] - dp[i - 1][j - 1];
		}
	}
	int start_x1 = 0, start_y1 = 0;
	int start_x2 = 0, start_y2 = 0;
	while (q-- > 0)
	{
		cin >> start_x1 >> start_y1 >> start_x2 >> start_y2;

		cout << dp[start_x2][start_y2] - dp[start_x1- 1][start_y2] - dp[start_x2][start_y1 - 1]
                +dp[start_x1 - 1][start_y1 - 1] << endl;
	}

	return 0;
}