2D prefix sums

2D prefix sums let a program answer many questions of the form "what is the sum of this rectangle of a table?" with four terms each, after one pass over the table. They work when the table doesn't change between the questions. If cells change in between, use a 2D Fenwick tree instead.

Explanation

A table has 4 rows and 5 columns of numbers. Rows are numbered from the top and columns from the left, both from 1. The question is the sum of rows 3 to 4, columns 3 to 5.

Fig. 1. The question asks for the sum of the blue rectangle.

Adding its six cells, 6 + 2 + 1 + 0 + 5 + 2 = 16, is fine once. But a program may get a table of 1000 \times 1000 cells and 10^6 questions. One rectangle can hold 10^6 cells, so adding up every question is up to 10^{12} steps, and about 10^8 steps fit in one second (time complexity).

Prefix sums answer the sum of a piece of one row with one subtraction. Row 3's prefix sums are 4 5 11 13 14, so columns 3–5 give 14 − 5 = 9. Row 4 gives 12 − 5 = 7 the same way, and 9 + 7 = 16. That is still one step per row. A question that covers 1000 rows costs 1000 steps, and 10^6 questions cost 10^9.

In one row, a prefix sum is the sum from the first cell. In a table, store for every cell the sum of the rectangle from the top-left cell to it. Call this the corner sum of the cell; the table of corner sums is called the 2D prefix sums. The question rectangle is the bottom-right part of the rectangle up to cell (4, 5), with corner sum 47. Above the question lie rows 1 to 2, the rectangle up to cell (2, 5), with corner sum 21. To its left lie columns 1 to 2, the rectangle up to cell (4, 2), with corner sum 18.

Fig. 2. The blue rectangle up to cell (4, 5) minus the two red rectangles should leave the question rectangle.

Add the rectangle up to (4, 5): every cell is counted once, 47.

Subtract the rectangle up to (2, 5): rows 1 and 2 are gone, 47 − 21 = 26.

Subtract the rectangle up to (4, 2): the red overlap is now counted −1 times, 26 − 18 = 8.

Add the rectangle up to (2, 2): the red overlap is back to 0, 8 + 8 = 16.

1/4

Fig. 3. Step through the four terms with the buttons or the arrow keys. The counter in each cell says how many times it is counted: blue cells once, red cells −1 times.

Rows 1–2, columns 1–2 are the overlap of the two removed rectangles. Four corner sums answer any rectangle: the one at its bottom-right corner, minus the one ending in the row just above it, minus the one ending in the column just left of it, plus the one ending at both. Removing two overlapping parts and adding back their overlap is called inclusion–exclusion.

Each corner sum is built with the same correction. The rectangle up to cell (3, 3) is the cell itself, plus the rectangle up to the cell above, plus the rectangle up to the cell on the left. Their overlap, the rectangle up to (2, 2), is in both, so it is subtracted once (Fig. 4). Row by row, left to right, the three corner sums a cell needs are always ready, so one pass builds them all.

Fig. 4. The corner sum of cell (3, 3) is the cell plus the two blue rectangles, minus their red overlap.

In C++

The table a is a 2D array with rows 1 to n and columns 1 to m. The corner sum of cell (i, j) is P[i][j]. Row 0 and column 0 of P are zeros, so a rectangle at the top or left edge needs no special case. With x the value of cell (i, j):

• build: P[i][j] = x + P[i - 1][j] + P[i][j - 1] - P[i - 1][j - 1];

• answer the question r1 c1 r2 c2 (rows r1 to r2, columns c1 to c2): P[r2][c2] - P[r1 - 1][c2] - P[r2][c1 - 1] + P[r1 - 1][c1 - 1].

For the question 3 3 4 5 this is P[4][5] - P[2][5] - P[4][2] + P[2][2] = 47 − 21 − 18 + 8 = 16: r1 - 1 = 2 is the last row above the question.

The input gives n and m, the table row by row, then the number of questions q and q lines r1 c1 r2 c2. For the table above and two questions:

4 5
2 0 3 1 4
1 5 2 0 3
4 1 6 2 1
3 2 0 5 2
2
3 3 4 5
2 2 4 4

#include <iostream>
#include <vector>
using namespace std;

int main() {
    // fast input: needed for a million questions
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<vector<long long>> P(n + 1, vector<long long>(m + 1, 0));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            // read
            long long x;
            cin >> x;
            // build
            P[i][j] = x + P[i - 1][j] + P[i][j - 1] - P[i - 1][j - 1];
        }

    // answer
    int q;
    cin >> q;
    while (q--) {
        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] << '\n';
    }
}

Building P takes O(n \cdot m) time and memory (about 8 MB for a 1000 \times 1000 table of long long), and each question takes $O(1)$.

Counting marked cells

A map shows trees as * and empty plots as ., one row per line. Build P over 1 for a tree and 0 for an empty plot, and the four terms count the trees in any rectangle.

// read row i of the map as a string s; cell (i, j) is s[j - 1]
// build
P[i][j] = (s[j - 1] == '*') + P[i - 1][j] + P[i][j - 1] - P[i - 1][j - 1];

The best k×k square

Try every bottom-right cell (i, j) of a k×k square, one question each, and keep the largest sum: O(n \cdot m) in total. The square ending at (i, j) covers rows i - k + 1 to i, so the row above it is i - k. On the first table, the best 2×2 square ends at (3, 3): 24 − 5 − 7 + 2 = 14.

long long best = LLONG_MIN;   // needs <climits>
for (int i = k; i <= n; i++)
    for (int j = k; j <= m; j++)
        best = max(best, P[i][j] - P[i - k][j] - P[i][j - k] + P[i - k][j - k]);

Adding to many rectangles

Sometimes many changes "add x to rows r1 to r2, columns c1 to c2" come first, and the final table is read after them. In 1D a difference array marks +x where a range starts and -x right after it ends. In 2D a rectangle gets four marks in a table d, and the corner sums of d are the final values.

A mark at (i, j) changes the value of every cell below and to the right of it. So a rectangle needs +x at its top-left cell, -x right after its last column, -x right after its last row, and +x where both minus marks act. Index r2 + 1 can be n + 1, so d has n + 2 rows and m + 2 columns. Each change costs $O(1)$, and the final build O(n \cdot m). Here P is a new table, built from d instead of a.

vector<vector<long long>> d(n + 2, vector<long long>(m + 2, 0));
// mark, for each change r1 c1 r2 c2 x
d[r1][c1] += x;
d[r1][c2 + 1] -= x;
d[r2 + 1][c1] -= x;
d[r2 + 1][c2 + 1] += x;
// build P from d: afterwards P[i][j] is the final value of cell (i, j)
P[i][j] = d[i][j] + P[i - 1][j] + P[i][j - 1] - P[i - 1][j - 1];

For example, a 4×5 table of zeros gets 3 added to rows 2–3, columns 2–4, and 1 added to rows 3–4, columns 3–5.

+3 at (2, 2): everything below and to the right gets 3.

−3 at (2, 5): column 5 returns to 0.

−3 at (4, 2): row 4 returns to 0, and cell (4, 5) is now −3.

+3 at (4, 5): cell (4, 5) returns to 0.

The second change adds its four marks: the overlap holds 3 + 1 = 4.

1/5

Fig. 5. Step through the marks with the buttons or the arrow keys. Each mark changes every value below and to the right of it.

Common mistakes

• Leaving out + P[r1 - 1][c1 - 1] in the question. On 3 3 4 5 it prints 8 instead of 16.

• Leaving out - P[i - 1][j - 1] in the build line. On the table above P[4][5] becomes 247 instead of 47, and every answer is wrong.

• Subtracting at r1 and c1 instead of r1 - 1 and c1 - 1. On 3 3 4 5 it prints 7 instead of 16.

• Making P of size n×m with indices from 0, so a question with r1 = 1 reads P[-1]. Give P a row 0 and a column 0 of zeros.

Similar techniques

When changes are mixed with questions, rebuilding P costs O(n \cdot m) per change; a 2D Fenwick tree does a change or a question in O(\log n \cdot \log m).

A sparse table answers the minimum or maximum of a range. A minimum can't be subtracted away, so P doesn't help there.

For the largest sum over all rectangles, trying each one with P is O(n^2 m^2). Fix two rows, add up each column between them, and find the maximum subarray of that row: O(n^2 m).

Practice