Precompute a 2D prefix-sum table so rectangular sum queries can be answered in constant time.
You are given a 2D integer matrix that does not change after it is created. Design a structure that can answer many queries asking for the sum of elements inside an axis-aligned submatrix.
Implement a class that precomputes enough information from the matrix so that each query can return the sum of all values in the rectangle defined by its top-left and bottom-right corners, inclusive.
Input Format
- First, an integer matrix
matrixwithmrows andncolumns. - Then multiple queries, each specified by four integers
row1,col1,row2, andcol2. - Each query asks for the sum of elements in the submatrix from
(row1, col1)to(row2, col2)inclusive.
Output Format
For each query, return the sum of all values inside the requested submatrix.
Constraints
- The matrix is immutable after initialization.
- Query coordinates are inclusive.
- A query rectangle is always valid.
- Use 0-based indexing unless otherwise specified by the platform API.
- A solution should support many queries efficiently after preprocessing.
Example 1
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
[8,11,12]
Explanation
Each query asks for the sum of one submatrix. Using a precomputed 2D prefix-sum table, each answer can be obtained in constant time.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.