306. Sub-matrix Sum Queries
Medium2-D Prefix Sum
Answer q queries: print the sum of the sub-matrix with top-left (r1, c1) and bottom-right (r2, c2), 1-based inclusive.
Input format
Line 1: r c Next r lines: c integers Next line: q Next q lines: r1 c1 r2 c2
Output format
One sum per line.
Example 1
Input
3 3 1 2 3 4 5 6 7 8 9 3 1 1 3 3 2 2 3 3 1 2 2 3
Output
45 28 16
Example 2
Input
1 1 5 1 1 1 1 1
Output
5
Constraints
1 ≤ r, c ≤ 500 1 ≤ q ≤ 10⁵
Read input from standard input and print the answer to standard output. Your code is judged against 4 test cases, most of them hidden.
Loading the MyLoginn IDE…