Increment Submatrices by One — Editorial

Opening the reading…

Intuitionwhy rectangle updates become row intervals

Updating every cell inside every query repeats work whenever rectangles are large or overlap. Instead, look at one row touched by a query: the query adds 1 to a continuous interval from col1 through col2. For an interval update, you only need to mark where the addition begins and where it ends. A later prefix sum carries that information across the interval.

Store +1 at col1 and -1 immediately after the interval, at col2 + 1. While scanning left to right, the running sum becomes larger at the start and returns to its old value after the end. A two-dimensional query is therefore a collection of one-dimensional interval updates, one for each row from row1 through row2.

A difference array stores interval boundaries instead of touching every cell.

Approachturn each rectangle into row events

Create an n by n + 1 difference matrix filled with zero, because every row needs a possible stop marker at column n when a query reaches the last real column.

For each query, read row1, col1, row2, and col2, then visit every row i from row1 through row2, because the rectangle contributes the same column interval to each of those rows.

At diff[i][col1], add 1 to mark where this query starts contributing, because the prefix sum must increase at the first covered column.

At diff[i][col2 + 1], subtract 1 to mark where the contribution stops, because every column after col2 must exclude this query; the extra column prevents an out-of-bounds write when col2 is n - 1.

After all queries are recorded, scan each row from column 0 to n - 1 while maintaining cur, because the running prefix sum combines every start and stop event that affects that cell.

Write cur into the answer matrix at each real column and return the matrix, because the sentinel column stores bookkeeping only and is not part of the required output.

Complexitythe row span of each query determines the update work

MEASURE	BOUND	WHY
Time	O(qn + n^2)	A query touches at most n rows and performs constant work on each, giving O(qn) in the worst case. The final prefix scan visits exactly n^2 output cells, so the two costs add rather than multiply.
Space	O(n^2) extra	The difference matrix has n rows and n + 1 columns. The returned n by n matrix is required output and is excluded from the extra-space bound; the working difference matrix remains O(n^2), including its worst shape when every query spans all rows.

Here q is the number of queries, and n is the matrix dimension.

Annotated solutionC++ · row-wise difference array · complete judge-ready version

CPPRecord two boundary events per affected row, then prefix-scan every row into the answer.

#include <vector>

using namespace std;

class Solution {
public:
    vector<vector<int>> rangeAddQueries(int n, vector<vector<int>>& queries) {
        vector<vector<int>> mat(n, vector<int>(n, 0));
        vector<vector<int>> diff(n, vector<int>(n + 1, 0));

        for (auto& q : queries) {
            int r1 = q[0];
            int c1 = q[1];
            int r2 = q[2];
            int c2 = q[3];

            for (int i = r1; i <= r2; ++i) {
                diff[i][c1] += 1;
                diff[i][c2 + 1] -= 1;
            }
        }

        for (int i = 0; i < n; ++i) {
            int cur = 0;
            for (int j = 0; j < n; ++j) {
                cur += diff[i][j];
                mat[i][j] = cur;
            }
        }

        return mat;
    }
};

The extra column is the small detail that makes the boundary formula uniform. Even when a query ends at the last real column, c2 + 1 equals n and is a valid index in diff. The reconstruction loop stops before that column, so the sentinel affects no output cell while still cleanly cancelling the query after the matrix ends.

The two-dimensional difference alternativea different arrangement with the same asymptotic space

You can also use a full two-dimensional difference array: add at the rectangle's top-left corner, subtract just below its bottom edge and just right of its right edge, then compensate at the diagonally opposite corner. Two prefix-sum passes reconstruct the matrix. This reduces each query to constant update work, but it makes the reconstruction more involved and still uses O(n^2) extra space.

CPPAn alternative that marks four rectangle corners and reconstructs with a two-dimensional prefix sum.

#include <vector>

using namespace std;

class Solution {
public:
    vector<vector<int>> rangeAddQueries(int n, vector<vector<int>>& queries) {
        vector<vector<int>> diff(n + 1, vector<int>(n + 1, 0));

        for (auto& q : queries) {
            int r1 = q[0];
            int c1 = q[1];
            int r2 = q[2];
            int c2 = q[3];

            diff[r1][c1] += 1;
            diff[r2 + 1][c1] -= 1;
            diff[r1][c2 + 1] -= 1;
            diff[r2 + 1][c2 + 1] += 1;
        }

        vector<vector<int>> mat(n, vector<int>(n, 0));
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                int top = (i > 0) ? mat[i - 1][j] : 0;
                int left = (j > 0) ? mat[i][j - 1] : 0;
                int diagonal = (i > 0 && j > 0) ? mat[i - 1][j - 1] : 0;
                mat[i][j] = diff[i][j] + top + left - diagonal;
            }
        }

        return mat;
    }
};