leetExpert
Practice

Range Sum Query 2D — Immutable

Module 12 · Prefix Sum

Problem

Given a 2D matrix, implement NumMatrix supporting sumRegion(row1, col1, row2, col2) — the sum of all elements inside that rectangle, inclusive — for many calls. The matrix never changes.

Examples

Example 1

InputNumMatrix([[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]]), sumRegion(2,1,4,3)Output8

Explanation. rows 2–4, cols 1–3: 2+0+1 + 1+0+1 + 0+3+0

Example 2

InputsumRegion(1,1,2,2)Output11

Example 3

InputsumRegion(1,2,2,4)Output12

Constraints

1 ≤ rows, cols ≤ 200 · up to 10⁴ calls to sumRegion.

Attempt it first

The direct application of the 2D prefix sum lesson, in the same class-shaped harness as Range Sum Query — Immutable. Build the padded 2D prefix array once in the constructor; answer each query with the four-term inclusion-exclusion formula.