Problem editorial

Range Sum Query 2D - Immutable

MediumArray/Matrix Manipulation PatternsArrayMatrixPrefix Sum

Range Sum Query 2D - Immutable: the approach in brief

The problem

Implement a class named NumMatrix for an integer matrix that remains unchanged after construction. If the matrix has m rows and n columns, rows are numbered from 0 to m - 1 and columns from 0 to n - 1.

Pattern

Range Sum Query 2D - Immutable is a Array/Matrix Manipulation Patterns problem, in the Prefix Sum - Subarray Sum / Range Query subpattern. The pattern covers in-place operations, hashing, prefix sums, spiral traversal, and cyclic sort

Approach outline

Avoid visiting every cell in a queried rectangle, since many queries may cover most of the matrix.
Precompute cumulative sums for rectangles that share the matrix's top-left corner.
Use inclusion-exclusion with the cumulative sums at the four corners surrounding the requested rectangle.

Complexity

The reference solution runs in O(mn) preprocessing and O(1) per sumRegion query time and O(mn) space.

The full editorial is part of Pro

It explains the core insight, the complexity analysis and the common mistakes, with a worked solution.

Unlock the full editorial with Pro Solve it first, free

Practise Range Sum Query 2D - Immutable and the problems around it

Range Sum Query 2D - Immutable is a Array/Matrix Manipulation Patterns problem, in the Prefix Sum - Subarray Sum / Range Query subpattern. Once the approach above makes sense, write it yourself and then work through the neighbouring problems that reuse it.

Range Sum Query 2D - Immutable