2D Range Update Point Query

Problem

Start with an n by m matrix of zeros and process operations: [1, r1, c1, r2, c2, value] adds value to the inclusive subrectangle, and [2, r, c] asks for the value at a cell. Return the query results in order.

Use a 2D difference array where each rectangle update touches four corners, and a query takes the 2D prefix sum.

Hint

The corner pattern is add at the top-left, subtract on the far edges, and add back at the opposite corner.

Test cases

case 1

in: [3,3,[[1,0,0,1,1,5],[2,0,0],[2,1,1],[2,2,2]]]

expected: [5,5,0]

case 2

in: [2,2,[[2,0,0]]]

expected: [0]

case 3

in: [1,1,[[1,0,0,0,0,7],[2,0,0]]]

expected: [7]

case 4

in: [3,3,[[1,1,1,2,2,3],[1,0,0,0,0,1],[2,1,2],[2,1,1],[2,0,0]]]

expected: [3,3,1]

Starter codePython

def matrix_range_update_queries(n, m, operations):
    # Your code here
    pass

4 test cases · run your code against them in the editor