2d_Prefix_Sum_Complete

#include<bits/stdc++.h>
using namespace std;
int main()
{
	/*

	given a n*m matrix (image), q users to use that software.
	every user -> Input->choose a submatrix output->sum of that submatrix.

	4 5
	2 3 1 4 5
	1 2 3 4 5
	0 2 3 0 1
	1 0 4 0 8
	3
	1 1 2 3  -> 14
	1 2 3 3  -> 14
	2 2 2 2  -> 3


	*/
	// int n, m; cin >> n >> m;//rows and colms
	// vector<vector<int>> v(n, vector<int>(m));//2d vector
	// for (int i = 0; i < n; i++) {//input matrix
	// 	for (int j = 0; j < m; j++) {
	// 		cin >> v[i][j];
	// 	}
	// }

	// int q; cin >> q;//users
	// while (q--) {
	// 	int a, b, c, d; cin >> a >> b >> c >> d;//input param for each user
	// 	int tempans = 0;
	// 	for (int i = a; i <= c; i++) {//ans calculated
	// 		for (int j = b; j <= d; j++) {
	// 			tempans += v[i][j];
	// 		}
	// 	}
	// 	cout << "User ans -> " << tempans << endl;
	// }

	//t.c-> O(Q*N*M)-->O(N^3)

	// vector<vector<int>> p(n + 1, vector<int>(m + 1, 0));//prefix matrix;
	// for (int i = 1; i <= n; i++) {
	// 	for (int j = 1; j <= m; j++) {
	// 		p[i][j] = v[i - 1][j - 1] + p[i - 1][j] + p[i][j - 1] - p[i - 1][j - 1];
	// 	}
	// }


	// for (int i = 0; i <= n; i++) {
	// 	for (int j = 0; j <= m; j++) {
	// 		cout << p[i][j] << " ";
	// 	}
	// 	cout << endl;
	// }




	// 2 3 1 4 5
	// 1 2 3 4 5
	// 0 2 3 0 1
	// 1 0 4 0 8

	// 0  0  0  0  0  0
	// 0  2  5  6  10 15
	// 0  3  8  12 20 30
	// 0  3  10 17 25 36
	// 0  4  11 22 30 49





	//now solving real question

	//input vector
	int n, m; cin >> n >> m;//rows and colms
	vector<vector<int>> v(n, vector<int>(m));//2d vector
	for (int i = 0; i < n; i++) {//input matrix
		for (int j = 0; j < m; j++) {
			cin >> v[i][j];
		}
	}

	//programmers had created a prefix matrix (with padding)
	vector<vector<int>> p(n + 1, vector<int>(m + 1, 0));//prefix matrix;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			p[i][j] = v[i - 1][j - 1] + p[i - 1][j] + p[i][j - 1] - p[i - 1][j - 1];
		}
	}

	//taking the users
	//perform the query for each.
	int q; cin >> q;
	for (int k = 1; k <= q; k++) {
		int a, b, c, d, ans = 0; cin >> a >> b >> c >> d;//start and end of submatrix

		//find ans;
		// 1.>0 indexing to 1 indexing
		a++; b++; c++; d++;//statement
		//2.>find ans;
		ans = p[c][d] - p[a - 1][d] - p[c][b - 1] + p[a - 1][b - 1];//mathmatical calculation->O(1)

		cout << "For User-> " << k << " " << "Answer is -> " << ans << endl;//answer printing

	}

//concept -> result -> optimised O(N^3) code to O(N) [in terms of query processing].
//T.c:O(N*M) + O(N*M) + O(Q) ====>O(N*M) ==> O(N^2)
	return 0;

}