Skills101
← All coding problems

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 r lines: c integers each
  • next line: q
  • next q lines: 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).

Loading editor…

Log in to run and submit your code — it's free.