Range Sum Query 2D - Immutable
mediumTime: O(1)Space: O(m*n)
Signals to notice
2D range sum queriesprecompute 2D prefix sumsinclusion-exclusion
Brute force first
Sum rectangle each query — O(mn).
The key insight
2D prefix sums. Query = inclusion-exclusion on 4 corners. O(mn) precompute, O(1) per query.
What must stay true
prefix[i][j] stores sum of rectangle (0,0)→(i-1,j-1). Sub-rectangle via 4 corners: add and subtract.
Easy way to go wrong
Getting the formula wrong — draw the 4 rectangles to visualize.