2D Range Sum Queries
mediumArrays & Prefix Sums+20 XPTime limit 2s
A farm is a grid of r × c plots; each plot has a yield (it can be negative after a bad season). Answer q questions: "what is the total yield of the rectangle with top-left plot (r1, c1) and bottom-right plot (r2, c2)?"
Input:
- line 1:
r c - next
rlines:cintegers each - next line:
q - next
qlines:r1 c1 r2 c2(1-based,r1 ≤ r2,c1 ≤ c2)
Output: q lines — the sum of each rectangle.
Constraints: 1 ≤ r, c ≤ 500, 1 ≤ q ≤ 10⁵, −10⁴ ≤ value ≤ 10⁴.
Think about it: build a 2D prefix sum: P[i][j] = sum of the rectangle from (1, 1) to (i, j). Then each query is P[r2][c2] − P[r1−1][c2] − P[r2][c1−1] + P[r1−1][c1−1] — the last term adds back the corner that was subtracted twice.
Sample input 1
3 4 1 2 3 4 5 6 7 8 9 10 11 12 3 1 1 3 4 2 2 3 3 1 4 1 4
Sample output 1
78 34 4
Sample input 2
1 1 -5 1 1 1 1 1
Sample output 2
-5
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).