143. Range Sum Query 2D

Given a 2D matrix and a list of queries [r1,c1,r2,c2] (inclusive rectangle corners), return the sum of all query results. Use a 2D prefix-sum for O(1) per query. Input: JSON {matrix, queries}.

Input: JSON {matrix, queries}.

Output: Integer — total of all query sums.

Examples

Input: {"matrix":[[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]],"queries":[[2,1,4,3],[1,1,2,2],[1,2,2,4]]}
Output: 33
Explanation: Sum of the three rectangle sums (8+11+14).

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

Constraints

• 1<=m,n<=200
• -10^5<=matrix[i][j]<=10^5
• 1<=queries.length<=10^4

Asked by