Learning pathOriginal reference
Lesson 9 of 12

Prefix sums in two dimensions

Use inclusion-exclusion for rectangles and marked-cell counts.

A prefix is now a corner rectangle

Define P[r][c] as the sum of rows 1 through r and columns 1 through c. Add a zero row and zero column to represent empty rectangles. To construct a cell, add the current value, the prefix above, and the prefix to the left, then subtract their shared upper-left overlap.

The recurrence is P[r][c] = a[r][c] + P[r − 1][c] + P[r][c − 1] − P[r − 1][c − 1]. Row-major order works because all three earlier entries are ready. An R-by-C matrix needs (R + 1)(C + 1) prefix entries; memory depends on the product of dimensions.

Cut off two strips and restore the overlap

For inclusive corners (r1, c1) and (r2, c2), start with P[r2][c2]. Subtract P[r1 − 1][c2] for the rows above and P[r2][c1 − 1] for the columns left. Their upper-left intersection was removed twice, so add P[r1 − 1][c1 − 1] once.

Build time is O(RC), each query is O(1), and all work is O(RC + q). Numeric sums use long long. Zero padding handles top and left boundaries without special cases.

C++23
// Complete C++23 program. Input: rows cols q, matrix, then r1 c1 r2 c2.
// Valid inclusive rectangles; rows,cols <= 500; |cell| <= 1e9.
#include <iostream>
#include <vector>
int main() {
    int rows, cols, q;
    std::cin >> rows >> cols >> q;
    std::vector<std::vector<long long>> pref(
        rows + 1, std::vector<long long>(cols + 1, 0));
    for (int r = 1; r <= rows; ++r) {
        for (int c = 1; c <= cols; ++c) {
            long long value;
            std::cin >> value;
            pref[r][c] = value + pref[r - 1][c] + pref[r][c - 1]
                       - pref[r - 1][c - 1];
        }
    }
    while (q--) {
        int r1, c1, r2, c2;
        std::cin >> r1 >> c1 >> r2 >> c2;
        std::cout << pref[r2][c2] - pref[r1 - 1][c2]
                   - pref[r2][c1 - 1] + pref[r1 - 1][c1 - 1] << '\n';
    }
}

A marked grid is another indicator sum

For a grid of # and ., use 1 for a marked cell and 0 otherwise. The same rectangle sum counts marked cells. With at most 500 × 500 cells, a count fits int; the input row string remains zero-based, so one-based column c uses row[c − 1].

Test a single cell, the full grid, top-row and left-column queries, and one-row or one-column matrices. Include nonsquare grids so swapped row and column dimensions cannot hide.

Pause & predict

Why is the upper-left overlap added back in a rectangle query?

Choose an answer
Try it yourself

Turn the idea into code

For rows [2,1,−1,3], [0,4,2,−2], [5,−3,1,2], find the sum of rows 2..3 and columns 2..4. Verify directly and with prefix corners.

Give me a hint

The desired cells are six values. The four needed prefix totals are 14, 5, 7, and 2.

Show the explained solution

Directly: 4 + 2 − 2 − 3 + 1 + 2 = 4. Inclusion-exclusion gives 14 − 5 − 7 + 2 = 4. Agreement verifies both the chosen rectangle and the corner formula.

Your notes

Ready for the next idea?

Mark complete when you can explain it yourself.

From a problem to a programIdentify the input, output, and constraints, then translate a small plan into C++.Variables, types, and remembered valuesChoose a representation, initialize it, and understand what assignment really changes.Arithmetic without surprisesPredict division and remainder, widen before multiplication, and format decimal answers.Conditions and logical decisionsBuild exclusive categories, combine comparisons, and protect operations with short-circuit logic.Optional: other ways to chooseRecognize switch for exact choices and the conditional operator for choosing a value.For loops: make repetition preciseTrace initialization, condition, body, and update—and avoid an extra iteration.While, do-while, and stopping rulesChoose a loop from its stopping condition and read the exact input format.Break, continue, and early answersDistinguish leaving a loop from skipping one iteration, without losing required input.Five patterns worth understandingUse sums, counts, best-so-far candidates, products, and flags to process a stream.Nested loops: rows and columnsTranslate a shape into two loop roles and count the total work.Take a number apart, one digit at a timeUse remainder and division to process decimal digits, including zero.Multiple cases and a debugging mindsetCombine the patterns, isolate each case, and test the boundaries that can break your idea.Arrays: give every value a placeUnderstand indices, initialization, capacity, active length, and the first safe array loop.Scan, count, search, and compareDistinguish values from positions and preserve the exact tie rule a problem asks for.Change a sequence without losing itUpdate, copy, compare, reverse, and inspect neighbours using the correct bounds.Matrices: think in two coordinatesTraverse tables, total rows and columns, inspect diagonals, and protect grid neighbours.Characters become stringsSeparate characters from numbers, then safely inspect and edit managed text.Read the text the problem actually givesChoose words or full lines, preserve empty cases, and reset only the state that needs it.Scan text: count, filter, transformBuild a result from matching characters without losing leading zeros or skipping shifted text.Join, compare, and find textLearn content comparison, lexicographical order, substring counts, and the not-found sentinel.