#207MediumPrefix Sums & Difference Arrays· 2D Prefix Sums

Region Rainfall Queries

A weather agency stores yesterday's rainfall (in millimetres) in a rectangular grid `grid`: one cell per map square, `grid[r][c]` being the rainfall of the square in row `r`, column `c`. Farmers phone in with rectangular regions and ask how much rain fell in total inside. Each query is `[r1, c1, r2, c2]`: the region whose top-left square is `(r1, c1)` and bottom-right square is `(r2, c2)`, both corners inclusive. Return the total rainfall of every query in order. There can be many queries on the same grid, so adding up each rectangle square by square is too slow.

Input format

`grid`: a rectangular matrix of integers. `queries`: a list of `[r1, c1, r2, c2]`.

Output format

An array with the total of each queried rectangle.

Examples

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

Output: [11, 21, 1]

The bottom-right 2 x 2 block holds 6 + 3 + 2 + 0 = 11. The whole grid sums to 21. The single square at row 0, column 2 holds 1.

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

Output: [8, 4]

A one-row grid works too: the whole row is 8 and the last square is 4.

Constraints

1 <= rows, cols <= 300
0 <= grid[r][c] <= 1000
1 <= queries.length <= 10^4
0 <= r1 <= r2 < rows and 0 <= c1 <= c2 < cols

#prefix-sums
#matrix
#2d-prefix-sums
#range-queries