A field is divided into a grid of plots; grid[r][c] is the yield of plot (r, c). Each query [r1, c1, r2, c2] asks for the total yield of the rectangular block with top-left corner (r1, c1) and bottom-right corner (r2, c2), both inclusive. Return one total per query.
Examples
Input: grid = [[1, 2, 3], [4, 5, 6], [7, 8, 9]], queries = [[0, 0, 1, 1], [1, 1, 2, 2], [0, 2, 2, 2]]
Output: [12, 28, 18]
Explanation: 1+2+4+5 = 12, 5+6+8+9 = 28 and the last column sums to 18.
Input: grid = [[5]], queries = [[0, 0, 0, 0]]
Output: [5]
Constraints
1 <= rows, cols <= 300,0 <= len(queries) <= 10**5-1000 <= grid[r][c] <= 1000,0 <= r1 <= r2 < rows,0 <= c1 <= c2 < cols- Target complexity: O(rows * cols + q). Summing each block cell by cell is too slow for the largest tests.
Goals
- Build a two-dimensional prefix table with one extra row and column
- Answer rectangle sums with four lookups via inclusion-exclusion