Fenwick 2D Prefix Sum

Problem

Support point updates and prefix-rectangle sums on a small 2D grid with a 2D Fenwick tree.

grid is the initial matrix. queries is a list of ["update", r, c, delta] (add delta at row r, column c) or ["prefix", r, c] (sum of the rectangle from (0,0) to (r,c) inclusive).

Return the list of prefix results.

Hint

The 2D BIT nests two index loops, each walking i += i & -i.

Test cases

case 1

in: [[[1,2],[3,4]],[["prefix",1,1]]]

expected: [10]

case 2

in: [[[1,2],[3,4]],[["prefix",0,1]]]

expected: [3]

case 3

in: [[[1,2],[3,4]],[["update",0,0,5],["prefix",1,1]]]

expected: [15]

case 4

in: [[[0,0],[0,0]],[["update",1,1,3],["prefix",1,1],["prefix",0,0]]]

expected: [3,0]

case 5

in: [[[2,2],[2,2]],[["prefix",0,0],["update",1,0,-2],["prefix",1,1]]]

expected: [2,6]

Starter codePython

def fenwick_2d(grid, queries):
    # Your code here
    pass

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