Range Sum Query 2D - Immutable

Medium · Arrays & Strings · about 20 minutes

Asked at Google, Meta, Amazon, Microsoft, Salesforce.

Answer many sub-rectangle sum queries on a fixed matrix.

• NumMatrix(matrix) stores the matrix.
• sumRegion(row1, col1, row2, col2) returns the sum of the rectangle with corners (row1, col1) (upper left)

and (row2, col2) (lower right), inclusive. Each query should be O(1).