Funcia
Lv.2gridprefix-sum

Rectangle Region Sums

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
0

For each query [r1, c1, r2, c2], return the sum of the rectangle from (r1, c1) to (r2, c2) (inclusive) of grid.

Examples

gridqueriesresult
[[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

  • 1≤H,W≤5001 \le H, W \le 500, −106≤-10^6 \le grid[i][j] ≤106\le 10^6, 1≤1 \le queries.length ≤200,000\le 200{,}000
  • 0≤r1≤r2<H0 \le r1 \le r2 < H, 0≤c1≤c2<W0 \le c1 \le c2 < W; sums can exceed 32 bits.

Expected complexity

Time
O(HW + Q)
Space
O(HW)

Examples

gridqueriesExpected
[[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 O(Q⋅HW)O(Q \cdot HW).

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)296 msestimated
C++ (GCC, gnu++23)296 msderived
Python 3.131000 msderived
Java 251996 msderived
Kotlin 2.4 (JVM)1592 msestimated
C# 14 (.NET 10)1592 msestimated

Test groups

GroupWeightTestsVisibility
sample02inputs and outputs
correctness406verdict only
performance604verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.