958. 2D Range Sum Queries (2D BIT / Prefix)

Given a matrix and a list of queries, each query [r1, c1, r2, c2] asks for the sum of the submatrix with corners (r1, c1) and (r2, c2) inclusive. Use a 2D prefix sum (or 2D BIT). Return the answers as an array in order. The input is JSON {matrix, queries}.

Input: JSON {matrix, queries}.

Output: Array — the submatrix sum for each query.

Examples

Input: {"matrix":[[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5]],"queries":[[0,0,1,1],[1,1,2,2]]}
Output: [14,11]
Explanation: Two submatrix sums.

Input: {"matrix":[[1]],"queries":[[0,0,0,0]]}
Output: [1]
Explanation: Single cell.

Input: {"matrix":[[1,2],[3,4]],"queries":[[0,0,1,1]]}
Output: [10]
Explanation: Whole matrix.

Constraints

• 1<=rows,cols<=1000
• 1<=queries<=10^4

Asked by