1116. Grid Totals With Updates

Hard7.5 points estimatedBinary Indexed TreeMatrixDesign3 hints
RPby Rohit Parihar

A solar farm is monitored as a grid of panels, and each cell holds the power (in watts, possibly negative for a panel that is drawing power) currently reported by one panel. Operators repeatedly overwrite single readings and ask for the total output of a rectangular block of panels. Design GridTotals to serve both kinds of request quickly.

  • GridTotals(grid) starts with the readings in grid (0-indexed rows and columns).
  • update(row, col, val) replaces the reading at (row, col) with val; it does not add to it.
  • sumRegion(row1, col1, row2, col2) returns the sum of all readings in the rectangle whose corners are (row1, col1) and (row2, col2), both corners included, with row1 <= row2 and col1 <= col2.

Recomputing a rectangle cell by cell on every query is too slow when queries are frequent.

Example 1

Input:
operations = ["GridTotals","sumRegion","update","sumRegion","sumRegion"]arguments = [[[[3,0,1],[2,5,4],[1,1,6]]],[0,0,1,1],[1,1,2],[0,0,1,1],[2,2,2,2]]
Output:
[null,10,null,7,6]
Explanation:

The top-left 2x2 block sums to 10; replacing the centre 5 with 2 lowers it to 7, and the bottom-right cell alone is 6.

Example 2

Input:
operations = ["GridTotals","sumRegion","update","sumRegion"]arguments = [[[[7]]],[0,0,0,0],[0,0,-3],[0,0,0,0]]
Output:
[null,7,null,-3]
Explanation:

A one-cell grid: the single reading is replaced, not added to, so the sum becomes -3.

Constraints

1 ≤ grid.length, grid[0].length ≤ 200 (the grid is rectangular)

-1000 ≤ grid[i][j], val ≤ 1000

At most 105 operations; every row, col and corner is inside the grid

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. operations names the class first and then each method call; arguments holds the arguments for each, in the same order. Your answer is one list with a result per operation - null for the constructor and for methods that return nothing.

Expected complexity

Time
O(log R * log C) per op
Space
O(R*C)

What the author was aiming for. Your own solution is not measured against it.

Asked in an interview

Were you asked this in an interview? Say where, anonymously.

Code
Loading the editor…

operations names the class, then each method to call; arguments holds one list of arguments per operation, in the same order.