All problems

Range Sum Query 2D

Medium · prefix sum

You are given a grid of integers grid and a list of rectangle questions queries. Rows and columns are counted from 0.

Each query is a list [r1, c1, r2, c2]. It describes the rectangle whose top-left cell is in row r1 and column c1, and whose bottom-right cell is in row r2 and column c2. Both corner cells are part of the rectangle, along with every cell between them.

Return a list with one number per query, in the same order: the sum of all numbers inside that rectangle.

Examples

Example 1

Input: grid = [[1, 2, 3], [4, 5, 6], [7, 8, 9]], queries = [[0, 0, 1, 1], [1, 1, 2, 2], [2, 0, 2, 2]]

Output: [12, 28, 24]

The first rectangle holds 1, 2, 4 and 5. The second holds 5, 6, 8 and 9. The third is the bottom row: 7 + 8 + 9.

Example 2

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

Output: [1, 2]

The right column adds to 4 + (-3) = 1. The whole grid adds to 2.

Example 3

Input: grid = [[5]], queries = [[0, 0, 0, 0]]

Output: [5]

A rectangle may be a single cell.

Constraints