Lv.2gridprefix-sum
Rectangle Region Sums
- Memory limit
- 256 MB
- Correctness time limit
- 10000 ms
- Solvers
- 0
For each query [r1, c1, r2, c2], return the sum of the rectangle from (r1, c1) to (r2, c2) (inclusive) of grid.
Examples
| grid | queries | result |
|---|---|---|
[[1, 2, 3], [4, 5, 6], [7, 8, 9]] | [[0, 0, 1, 1], [1, 1, 2, 2], [0, 0, 2, 2], [2, 0, 2, 0]] | [12, 28, 45, 7] |
[[-3, 5]] | [[0, 1, 0, 1], [0, 0, 0, 1]] | [5, 2] |
Efficiency
This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.
Function signature
solution(grid: int[][], queries: int[][]) → long[]
Constraints
- ,
grid[i][j],queries.length - , ; sums can exceed 32 bits.
Expected complexity
- Time
- O(HW + Q)
- Space
- O(HW)
Examples
| grid | queries | Expected |
|---|---|---|
[[1,2,3],[4,5,6],[7,8,9]] | [[0,0,1,1],[1,1,2,2],[0,0,2,2],[2,0,2,0]] | [12,28,45,7] |
[[-3,5]] | [[0,1,0,1],[0,0,0,1]] | [5,2] |
Hint
Hint
Build a 2D prefix sum S of size (H+1) × (W+1) and answer with inclusion–exclusion:
S[r2+1][c2+1] - S[r1][c2+1] - S[r2+1][c1] + S[r1][c1]. Summing each rectangle directly is .
Time limits per language
| Language | Efficiency time limit | |
|---|---|---|
| C (GCC, gnu17) | 296 ms | estimated |
| C++ (GCC, gnu++23) | 296 ms | derived |
| Python 3.13 | 1000 ms | derived |
| Java 25 | 1996 ms | derived |
| Kotlin 2.4 (JVM) | 1592 ms | estimated |
| C# 14 (.NET 10) | 1592 ms | estimated |
Test groups
| Group | Weight | Tests | Visibility |
|---|---|---|---|
| sample | 0 | 2 | inputs and outputs |
| correctness | 40 | 6 | verdict only |
| performance | 60 | 4 | verdict only |