Medium · prefix sums

2D Range Sums

The 1D trick was one subtraction. In two dimensions every prefix is a rectangle, so a sub-rectangle needs you to subtract two strips and add back the corner you subtracted twice — one drawn picture is worth more than the formula.

At a glanceBuild <code>P[i][j]</code> = sum of rows 1..i, cols 1..j; then any rectangle (r1,c1,r2,c2) is <code>P[r2][c2] - P[r1-1][c2] - P[r2][c1-1] + P[r1-1][c1-1]</code>.

Problem

Input: The first line has n, m and q (1 ≤ n, m ≤ 50, 1 ≤ q ≤ 100). Then n lines of m integers (0 ≤ a ≤ 1000). Then q lines: r1 c1 r2 c2 (1 ≤ r1 ≤ r2 ≤ n, 1 ≤ c1 ≤ c2 ≤ m).

Output: q lines: for each query, the sum of the rectangle, one per line.

Samples:

Input	Output
`2 2 3 1 2 3 4 1 1 2 2 1 1 1 1 2 2 2 2`	`10 1 4`

Rows count first, then columns — the same convention as Sum a Matrix. A single cell (r1 = r2, c1 = c2) is a legal rectangle, and so is the whole grid.

Your solution

main.cpp — your solution

Custom input for "Run my input"

Judging runs in your browser against hidden tests. A runaway loop is cut off after 3 seconds — still, make sure every loop has an exit. Your code is saved in this browser as you type.

Stuck? Hints

Hint 1 — Pad the table with a zero row and column

Declare P[55][55] and leave row 0 and column 0 as zeros. Then the build formula P[i][j] = P[i-1][j] + P[i][j-1] - P[i-1][j-1] + a[i][j] works for i = 1 and j = 1 without any special cases — exactly the trick that made the 1D version clean.

Hint 2 — Draw the four corners

Before memorizing the query formula, draw two rectangles: the big prefix (1,1)-(r2,c2) and the wanted one (r1,c1)-(r2,c2). The two strips you must remove are above and to the left, and they overlap in the top-left corner — subtract both strips, add that corner back once. The formula stops being magic once you have seen the picture.

Hint 3 — Reuse the build for the query

The build rule and the query rule are the same picture read in different directions: build adds a cell to three prefixes; a query subtracts strips from one big prefix. If your build passes the samples but queries fail, the bug is almost always in the corner signs of the query line, not in the build.

Solution (try it first!)

#include <iostream>
using namespace std;

int P[55][55];

int main() {
    int n, m, q;
    cin >> n >> m >> q;

    for (int j = 0; j <= m; j++) P[0][j] = 0;
    for (int i = 0; i <= n; i++) P[i][0] = 0;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            int a;
            cin >> a;
            P[i][j] = P[i - 1][j] + P[i][j - 1] - P[i - 1][j - 1] + a;
        }
    }

    for (int k = 0; k < q; k++) {
        int r1, c1, r2, c2;
        cin >> r1 >> c1 >> r2 >> c2;
        cout << P[r2][c2] - P[r1 - 1][c2] - P[r2][c1 - 1] + P[r1 - 1][c1 - 1] << endl;
    }
    return 0;
}

You now own the 2D version of pay-once-answer-many: the 1D original lives in Range Sum Queries, and the same inclusion-exclusion corner will reappear when you meet counting problems on grids. The general lesson survives both: precompute the structure the queries imply, then make each question cheap.

Deep dive

Why this works

Define P[i][j] as the total of rows 1..i and columns 1..j. Any rectangle then telescopes by inclusion-exclusion: the big prefix minus the strip above minus the strip left, plus their shared corner (subtracted twice, so add once). Build and query are the same picture read in opposite directions.

The cost

O(n·m) to build, O(1) per query, O(n·m) space. Summing each rectangle by brute force is O(n·m) per query — with q = 100 queries on a 50×50 grid that is 250,000 additions versus 100 subtractions.

Where it goes wrong

Forgetting + P[i-1][j-1] in the query — the top-left corner was subtracted twice and must be added back once. Queries that touch row 1 or column 1 hide the bug (those strips are zero).
Reusing the grid array in place while building P: P[i][j] += a after reading into the same 2D array works, but mixing indices (a[i][j] vs P[i-1][j-1]) off by one is the classic silent corruption.
Row/column order: the statement is rows first (n rows of m values). Swapping them happens to work on square samples and fails on rectangular tests.

Next step

The 1D original is Range Sum Queries — read the two side by side and the inclusion-exclusion becomes obvious. The next structure for grids is the 2D difference array (updates + queries together).

Two things to remember

P[i][j] = rows 1..i, cols 1..j; a rectangle = big − top − left + corner.
Pad row 0 and column 0 with zeros and every formula loses its special cases.

🐞 This version fails — open it and try

Drops the corner — the top-left prefix was subtracted twice and never added back

#include <iostream>
using namespace std;

int P[55][55];

int main() {
    int n, m, q;
    cin >> n >> m >> q;
    for (int j = 0; j <= m; j++) P[0][j] = 0;
    for (int i = 0; i <= n; i++) P[i][0] = 0;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            int a;
            cin >> a;
            P[i][j] = P[i - 1][j] + P[i][j - 1] - P[i - 1][j - 1] + a;
        }
    }
    for (int k = 0; k < q; k++) {
        int r1, c1, r2, c2;
        cin >> r1 >> c1 >> r2 >> c2;
        cout << P[r2][c2] - P[r1 - 1][c2] - P[r2][c1 - 1] << endl;  // bug: no + corner
    }
    return 0;
}