Given a 2D integer array grid, implement a class MatrixSumQuery2D that supports the following operations: 1) MatrixSumQuery2D(grid): initialize the object with the grid. 2) sum_submatrix(r1, c1, r2, c2): return the sum of all elements in the submatrix defined by the upper-left corner (r1, c1) and lower-right corner (r2, c2), inclusive. The sum_submatrix method must operate in O(1) time per query.
Example 1
Input: grid = [[2, 1, 4], [3, 5, 6], [7, 8, 9]] queries = [(0, 0, 1, 1), (1, 1, 2, 2), (0, 2, 2, 2)]
Output: [11, 28, 19]
Explanation: First query sums [[2,1],[3,5]] = 2+1+3+5=11; Second query sums [[5,6],[8,9]] = 5+6+8+9=28; Third query sums [4,6,9]=4+6+9=19.
Example 2
Input: grid = [[-1, 2], [3, -4]] queries = [(0, 0, 1, 1), (0, 1, 1, 1)]
Output: [0, -2]
Explanation: First query sums all elements: -1+2+3-4=0; Second query sums [2,-4]=2-4=-2.
Constraints
Case 1
Input: grid = [[5, 3, 1], [2, 4, 6], [7, 8, 9]] queries = [(0, 0, 2, 2), (1, 1, 2, 2), (0, 1, 1, 2)]
Expected: [45, 27, 14]
Case 2
Input: grid = [[0, 0, 0], [0, 0, 0], [0, 0, 0]] queries = [(0, 0, 2, 2), (1, 1, 1, 1)]
Expected: [0, 0]
Case 3
Input: grid = [[1]] queries = [(0, 0, 0, 0)]
Expected: [1]
Case 4
Input: grid = [[10, -10], [-10, 10]] queries = [(0, 0, 1, 1), (0, 1, 1, 1)]
Expected: [0, 0]