2D Array Range Sum

Interview

Time limit2sMemory limit128 MB

Summary
Build a 2D prefix sum over an N by M grid and answer up to 10,000 rectangle sum queries in O(1) each.
Level

Easy3 of 10

Topics
Prefix sum, Matrix, Array
Solved
No attempts yet

Problem

You are given an N by M array of integers. For each query, compute the sum of all numbers in the rectangular region whose top-left position is (i, j) and bottom-right position is (x, y).

The position (i, j) means row i and column j.

Input

The first line contains the array dimensions N and M. (1 <= N, M <= 300)

Each of the next N lines contains M integers, describing one row of the array. Every number in the array has absolute value at most 10,000.

The next line contains K, the number of rectangular-sum queries. (1 <= K <= 10,000)

Each of the next K lines contains four integers i, j, x, and y. This asks for the sum from (i, j) to (x, y), and it always satisfies 1 <= i <= x <= N and 1 <= j <= y <= M.

Output

For each query, in the order given, print the sum of the numbers in the requested rectangle on its own line. Each sum is at most 2^31 - 1.

Examples1

  1. Example 1

    Input
    2 3
1 2 4
8 16 32
3
1 1 2 3
1 2 1 2
1 3 2 3
    Expected output
    63
2
36