Range Sum Query 2D - Immutable
mediumTime: O(1)Space: O(m*n)
Recognize the pattern
2D range sum queriesprecompute 2D prefix sumsinclusion-exclusion
Brute force idea
Sum rectangle each query — O(mn).
Better approach
2D prefix sums. Query = inclusion-exclusion on 4 corners. O(mn) precompute, O(1) per query.
Key invariant
prefix[i][j] stores sum of rectangle (0,0)→(i-1,j-1). Sub-rectangle via 4 corners: add and subtract.
Watch out for
Getting the formula wrong — draw the 4 rectangles to visualize.