All problems
Fenwick 2D Range Update Point Query
Problem
Support rectangle additions and point queries on a 2D grid.
grid is the initial matrix. operations contains ["add", r1, c1, r2, c2, val] (add val to every cell of the inclusive rectangle) or ["point", r, c] (current value). A 2D difference array indexed by a 2D Fenwick tree turns each rectangle add into four corner updates.
Return the list of point queries.
Hint
A rectangle add on a difference array is four point updates at the corners.
Test cases
case 1
in: [[[1,2],[3,4]],[["point",0,0],["add",0,0,1,1,5],["point",1,1]]]
expected: [1,9]
case 2
in: [[[0,0],[0,0]],[["add",0,0,0,0,3],["point",0,0],["point",1,1]]]
expected: [3,0]
case 3
in: [[[1]],[["point",0,0],["add",0,0,0,0,-1],["point",0,0]]]
expected: [1,0]
case 4
in: [[[1,2,3],[4,5,6]],[["add",1,1,1,2,10],["point",0,1],["point",1,2]]]
expected: [2,16]
Starter codePython
def fenwick_2d_range_update(grid, queries):
# Your code here
pass4 test cases · run your code against them in the editor