Rectangle sum queries
Your task
You are given a rectangular grid of integers (a non-empty list of equal-length rows) and a batch of rectangle queries. Each query is [r1, c1, r2, c2] with 0 <= r1 <= r2 and 0 <= c1 <= c2, all inside the grid, and asks for the sum of every cell in that inclusive rectangle. Return the answers in order, computing each query in constant time after preprocessing. Example: grid = [[1, 2], [3, 4]], queries = [[0, 0, 1, 1], [0, 1, 1, 1]] gives [10, 6].
Examples
rectangle_sums(grid: list[list[int]], queries: list[list[int]]) -> list[int]Example 1
Input
rectangle_sums([[1, 2], [3, 4]], [[0, 0, 1, 1], [0, 1, 1, 1]])Output
[10, 6]