2D Prefix Sum Range Query

Problem

Answer axis-aligned rectangle sum queries on a matrix, where each query is [r1, c1, r2, c2] with inclusive bounds.

Build a 2D prefix sum table where each entry is the sum of the rectangle from the origin, then combine four table entries per query. Return the query answers in order.

Hint

Inclusion-exclusion adds the bottom-right corner and subtracts the two strips plus the overlap.

Test cases

case 1

in: [[[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]],[[2,1,4,3],[1,1,2,2],[1,2,2,4]]]

expected: [8,11,12]

case 2

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

expected: [10,1,4]

case 3

in: [[[5]],[[0,0,0,0]]]

expected: [5]

Starter codePython

def matrix_sum_queries(matrix, queries):
    # Your code here
    pass

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