Given a matrix Arr of size N x M. You are given position of submatrix as X_{1}, Y_{1} and X_{2}, Y_{2} inside the matrix. Find the sum of all elements inside that submatrix. Here X_{1}, Y_{1}, X_{2}, Y_{2} are 1-based.
Example 1:
Input: 
N = 5 , M = 6
Arr[][] = {{1, 2, 3, 4, 5, 6},
           {7, 8, 9, 10, 11, 12},
           {13, 14, 15, 16, 17, 18},
           {19, 20, 21, 22, 23, 24},
           {25, 26, 27, 28, 29, 30}}
X_{1}=3, Y_{1}=4, X_{2}=4, Y_{2}=5
Output: 78
Explanation: Sum from cell starting at
position (3, 4) (1-based indexing) and 
ending at (4, 5) is 78.
Example 2:
Input: 
N = 3, M = 3
Arr[][] = {{9, 8, 7},{4, 2, 1},{6, 5, 3}}
X_{1}=1, Y_{1}=2, X_{2}=3, Y_{2}=3
Output: 26
Explanation: Sum from cell starting at
position (1, 2) (1-based indexing) and 
ending at (3, 3) is 26.
Your Task:  
You don't need to read input or print anything. Your task is to complete the function subMatrixSum() which takes the array of booleans arr[][], n, m, x1, y1, x2 and y2 as parameters and returns an integer denoting the answer.
Expected Time Complexity: O(N*M)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N, M ≤ 10^{3}
1 ≤ Arr[N][M] ≤ 10^{6}
1 <= X_{1}, X_{2 }<= N
1 <= Y_{1}, Y_{2 }<= M

Difficulty: EASY
Tags: Data structures
Skill types: Data structures
Expected Time Complexity: O(N*M)
Expected Auxiliary Space: O(1)

Starter code:
#User function Template for python3

class Solution:



	def subMatrixSum(self,arr, n, m, x1, y1, x2, y2):

		# code here

Solutions:
class Solution:

	def subMatrixSum(self, arr, n, m, x1, y1, x2, y2):
		sum = 0
		x1 = x1 - 1
		y1 = y1 - 1
		x2 -= 1
		y2 -= 1
		for i in range(x1, x2 + 1):
			for j in range(y1, y2 + 1):
				sum += arr[i][j]
		return sum


class Solution:

	def subMatrixSum(self, arr, n, m, x1, y1, x2, y2):
		x1 -= 1
		y1 -= 1
		x2 -= 1
		y2 -= 1
		total = 0
		for i in range(n):
			if i >= x1 and i <= x2:
				for j in range(m):
					if j >= y1 and j <= y2:
						total += arr[i][j]
		return total


class Solution:

	def subMatrixSum(self, arr, n, m, x1, y1, x2, y2):
		return sum((sum(row[y1 - 1:y2]) for row in arr[x1 - 1:x2]))


class Solution:

	def subMatrixSum(self, Arr, n, m, X1, Y1, X2, Y2):
		X1 -= 1
		X2 -= 1
		Y1 -= 1
		Y2 -= 1
		pfm = Arr.copy()
		for i in range(len(Arr)):
			for j in range(1, len(Arr[i])):
				pfm[i][j] = pfm[i][j - 1] + Arr[i][j]
		for i in range(len(Arr[0])):
			for j in range(1, len(Arr)):
				pfm[j][i] = pfm[j - 1][i] + Arr[j][i]
		s = Arr[X2][Y2]
		if Y1 > 0:
			s = s - Arr[X2][Y1 - 1]
		if X1 > 0:
			s = s - Arr[X1 - 1][Y2]
		if X1 > 0 and Y1 > 0:
			s = s + Arr[X1 - 1][Y1 - 1]
		return s


class Solution:

	def subMatrixSum(self, arr, n, m, x1, y1, x2, y2):
		x1 = x1 - 1
		y1 = y1 - 1
		x2 = x2 - 1
		y2 = y2 - 1
		prefix_sum = [[0 for i in range(m)] for j in range(n)]
		for i in range(n):
			for j in range(m):
				if j == 0:
					prefix_sum[i][j] = arr[i][j]
				else:
					prefix_sum[i][j] = prefix_sum[i][j - 1] + arr[i][j]
		for j in range(m):
			for i in range(1, n):
				prefix_sum[i][j] = prefix_sum[i - 1][j] + prefix_sum[i][j]
		resultant_value = 0
		resultant_value += prefix_sum[x2][y2]
		if x1 > 0:
			resultant_value -= prefix_sum[x1 - 1][y2]
		if y1 > 0:
			resultant_value -= prefix_sum[x2][y1 - 1]
		if x1 > 0 and y1 > 0:
			resultant_value += prefix_sum[x1 - 1][y1 - 1]
		return resultant_value


class Solution:

	def subMatrixSum(self, arr, n, m, x1, y1, x2, y2):
		i = x1 - 1
		ans = 0
		while i < x2 and i < n:
			j = y1 - 1
			while j < y2 and j < m:
				ans += arr[i][j]
				j += 1
			i += 1
		return ans


class Solution:

	def subMatrixSum(self, arr, n, m, x1, y1, x2, y2):
		sum = 0
		for i in range(n):
			for j in range(m):
				if (i >= x1 - 1 and j >= y1 - 1) and (i <= x2 - 1 and j <= y2 - 1):
					sum += arr[i][j]
		return sum
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		(n, m) = list(map(int, input().strip().split()))
		inputLine = list(map(int, input().strip().split()))
		arr = [[0 for j in range(m)] for i in range(n)]
		for i in range(n):
			for j in range(m):
				arr[i][j] = inputLine[i * m + j]
		(x1, y1, x2, y2) = list(map(int, input().strip().split()))
		ob = Solution()
		ans = ob.subMatrixSum(arr, n, m, x1, y1, x2, y2)
		print(ans)
		tc -= 1


import numpy as np

class Solution:

	def subMatrixSum(self, arr, n, m, x1, y1, x2, y2):
		a = np.array(arr)
		X = list(np.arange(x1 - 1, x2))
		Y = list(np.arange(y1 - 1, y2))
		b = a[np.ix_(X, Y)]
		return np.sum(b)


class Solution:

	def subMatrixSum(self, arr, n, m, x1, y1, x2, y2):
		subrow1 = x1 - 1
		subrow2 = x2 - 1
		subcol1 = y1 - 1
		subcol2 = y2 - 1
		sum = 0
		for i in range(subrow1, x2, 1):
			for j in range(subcol1, y2, 1):
				sum += arr[i][j]
		return sum


class Solution:

	def subMatrixSum(self, a, n, m, x1, y1, x2, y2):
		s = 0
		for i in range(x1 - 1, x2):
			for j in range(y1 - 1, y2):
				s += a[i][j]
		return s