noodleProblems/
Range Sum Query 2D - Immutable
#129

Range Sum Query 2D - Immutable

AlgorithmmediumArrayMatrixPrefix SumDesign

Given an integer matrix that is never modified, answer a batch of 2D range-sum queries. Each query is [r1, c1, r2, c2] (0-based) and asks for the sum of every element inside the rectangle whose top-left corner is (r1, c1) and bottom-right corner is (r2, c2), **inclusive** of all four edges.

Return an array whose k-th entry is the answer to the k-th query. Because the matrix is immutable, precompute a 2D prefix-sum table once and answer every query in constant time.

Example cases

  • two rectangles
    in matrix =
    30142
    56321
    12015
    41017
    10305
    queries =
    2143
    1122
    out [8,11]
    Rectangle (2,1)-(4,3) sums to 8; rectangle (1,1)-(2,2) sums to 6+3+2+0 = 11.
  • single cell
    in matrix =
    12
    34
    queries =
    0000
    1111
    out [1,4]
  • whole matrix
    in matrix =
    12
    34
    queries =
    0011
    out [10]
  • no queries
    in matrix =
    5
    queries = []
    out []

Constraints

  • 0 <= matrix.length, matrix[0].length <= 200
  • -10^5 <= matrix[r][c] <= 10^5
  • 0 <= queries.length <= 10^4
  • 0 <= r1 <= r2 < matrix.length and 0 <= c1 <= c2 < matrix[0].length
Saved
matrix =
[[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]]
queries =
[[2,1,4,3],[1,1,2,2]]