Medium · Dynamic Programming

Range Sum Query 2D - Immutable

Given an m × n integer matrix that never changes and a query (row1, col1, row2, col2) with row1 ≤ row2 and col1 ≤ col2, return the sum of the cells in the inclusive rectangle from (row1, col1) to (row2, col2); preprocessing should make each such query O(1).

Examples

Example 1

{
  "matrix": [
    [3, 0, 1, 4],
    [5, 6, 3, 2],
    [1, 2, 0, 1]
  ],
  "row1": 1,
  "col1": 1,
  "row2": 2,
  "col2": 2
}

Output: sum = 11

Example 2

{
  "matrix": [
    [3, 0, 1, 4],
    [5, 6, 3, 2],
    [1, 2, 0, 1]
  ],
  "row1": 0,
  "col1": 0,
  "row2": 1,
  "col2": 1
}

Output: sum = 14

Rebuild it in the studio

Read every interview problem free. Ten rooms need no account. A token opens a problem in full — Pro never counts.