78. Region Totals
A city planner keeps a rectangular grid in which each cell holds the number of new trees planted in that block. Residents keep asking about the total number of trees inside rectangular neighbourhoods, so the planner wants a helper class that answers such queries quickly.
Implement the class RegionTotals. The constructor RegionTotals(grid) receives the 2-D integer array grid once and returns nothing. The method sumRegion(row1, col1, row2, col2) returns the sum of all cells grid[r][c] with row1 <= r <= row2 and col1 <= c <= col2. The grid is never modified between calls.
Example 1
- Input:
- operations = ["RegionTotals","sumRegion","sumRegion","sumRegion"]arguments = [[[[1,2,3,4],[5,6,7,8],[9,10,11,12]]],[0,0,1,1],[1,1,2,3],[2,0,2,0]]
- Output:
- [null,14,54,9]
- Explanation:
The top-left 2x2 block sums to 1+2+5+6=14, the lower-right 2x3 block to 54, and the single cell at row 2, column 0 is 9.
Example 2
- Input:
- operations = ["RegionTotals","sumRegion","sumRegion"]arguments = [[[[-3,4],[2,-1]]],[0,0,1,1],[0,1,1,1]]
- Output:
- [null,2,3]
- Explanation:
The whole grid sums to 2 and the right column sums to 3.
Constraints
1 ≤ grid.length, grid[i].length ≤ 200
-1000 ≤ grid[i][j] ≤ 1000
0 ≤ row1 ≤ row2 < grid.length, 0 ≤ col1 ≤ col2 < grid[0].length
At most 104 calls to sumRegion
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Input
- Each case is an operation log.
operationsnames the class first and then each method call;argumentsholds the arguments for each, in the same order. Your answer is one list with a result per operation -nullfor the constructor and for methods that return nothing.
Expected complexity
- Time
- O(m*n) build, O(1) per query
- Space
- O(m*n)