Back to DSA sheet
Range Sum Query 2D Immutable
MediumArraysGiven a fixed matrix, answer queries for the sum of the submatrix between (r1,c1) and (r2,c2) inclusive. Precompute so each query is O(1).
Input format (stdin): line 1 has rows and cols; the next rows lines each have cols integers; then a line with q; each of the next q lines has r1 c1 r2 c2. Output each query sum on its own line.
Examples
Input: 3 3
1 2 3
4 5 6
7 8 9
2
0 0 1 1
1 1 2 2
Output: 12
28
Top-left 2x2 sums to 12; bottom-right 2x2 sums to 28.
Constraints
- 1 <= rows, cols <= 200
- 1 <= q <= 10^4
Sheets
NeetCode 250
range-sum-query-2d-immutable.cpp1 sample tests
Loading editor
Test results
Run the sample tests to check your solution against expected output.
Custom input (stdin)
Output
Run your code to see its output.