Total Area Score: Compute Aggregate Score Over Rectangular Regions in a Grid

Question

## Problem

You are given an `m x n` grid of integers. For a list of queries, each query specifies a rectangle `(r1, c1, r2, c2)` (inclusive). Return the sum of all values in the rectangle for each query.

```python
class GridScorer:
    def __init__(self, grid: list[list[int]]):
        pass

def query(self, r1: int, c1: int, r2: int, c2: int) -> int:
        pass
```

**Example:**
```
Grid:
  [[3, 0, 1, 4],
   [5, 6, 3, 2],
   [1, 2, 0, 1]]

query(1, 1, 2, 2) -> 6+3+2+0 = 11
query(0, 0, 2, 3) -> sum of entire grid = 28
```

## Approach

Build a 2D prefix sum table in `__init__` (O(m*n)). Each query is then O(1) using inclusion-exclusion:
`sum(r1,c1,r2,c2) = P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1]`

## Follow-ups

1. What is the time complexity of preprocessing and each query?
2. How would you handle updates to individual cells efficiently? (hint: segment tree or BIT)
3. Extend to 3D: compute the sum in a rectangular cuboid.
4. What if queries can have weights and you need the weighted sum of region scores?

Total Area Score: Compute Aggregate Score Over Rectangular Regions in a Grid

Question Details

Full Details

Topics

More from Airbnb