Arrays and Hashing Prefix sums

77. Range Sum Query 2D - Immutable

Medium

You are given a grid of integers grid with m rows and n columns, and a list of queries. Rows and columns are numbered from 0, and the cell in row r and column c is grid[r][c].

Each query is [r1, c1, r2, c2]. It describes a rectangle whose top-left cell is (r1, c1) and whose bottom-right cell is (r2, c2). Both corners are inside the rectangle.

Return an array answer with one number per query, where answer[k] is the sum of every cell inside the rectangle of queries[k].

Example 1

Input: grid = [[2, 0, 1, 3], [4, -1, 2, 0], [1, 5, -2, 6]] queries = [[0, 0, 1, 1], [1, 1, 2, 3], [0, 0, 2, 3], [2, 2, 2, 2]]

Output: [5,10,21,-2]

Explanation: The first rectangle holds 2, 0, 4 and −1, which add up to 5. The second covers columns 1 to 3 of the last two rows: −1 + 2 + 0 + 5 − 2 + 6 = 10. The third is the whole grid, and the fourth is the single cell grid[2][2].

Example 2

Input: grid = [[-7]] queries = [[0, 0, 0, 0], [0, 0, 0, 0]]

Output: [-7,-7]

Explanation: The grid has one cell, so every query covers it. The same query can appear more than once, and each one gets its own answer.

Example 3

Input: grid = [[1000000000, 1000000000], [1000000000, 1000000000]] queries = [[0, 0, 1, 1], [0, 1, 1, 1]]

Output: [4000000000,2000000000]

Explanation: The whole grid adds up to 4 × 10⁹, which is more than a 32-bit integer can hold. The right column adds up to 2 × 10⁹, which still fits.

Check your understanding

Work out the answer for this input before you write any code.

grid = [[1, 2], [3, 4]], queries = [[1, 0, 1, 1]]

Constraints

m == grid.length, n == grid[i].length
1 ≤ m, n and m × n ≤ 10⁵
-10⁹ ≤ grid[i][j] ≤ 10⁹
1 ≤ queries.length ≤ 10⁵
queries[k] == [r1, c1, r2, c2]
0 ≤ r1 ≤ r2 < m and 0 ≤ c1 ≤ c2 < n

Clarifying questions

What you would ask an interviewer before writing any code.