LeetCode Daily Problem P2536 Submatrix Element Add 1

---

Timeline

Timeline

2025-11-14

init

Difference and prefix sum are inverse operations

---

Problem:

P2536 Submatrix element add 1

https://leetcode.cn/problems/increment-submatrices-by-one/description/?envType=daily-question&envId=2025-11-14

A template problem for difference matrix, which can be generalized to adding other integers to submatrices, not limited to +1. Performing O(1) operations on the difference matrix leaves traces of adding 1 to the submatrix. Then, using the property that prefix sum and difference are inverse operations, computing the prefix sum of the difference matrix yields the answer.

2D difference and its prefix sum

The prefix sum of a 2D difference refers to the sum of the matrix from (0,0) to (i,j)

Note the size of the difference matrix! It should be one larger than the original matrix in each dimension

#include <vector>
using std::vector;

class Solution {
    public:
	vector<vector<int> > rangeAddQueries(int n, vector<vector<int> > &queries)
	{
		vector<vector<int> > mat(n, vector<int>(n, 0));
		// Difference matrix
		vector<vector<int> > diff(n + 1, vector<int>(n + 1, 0));
		int row1, col1, row2, col2;
		int x1, x2, x3;
		for (const auto &query : queries) {
			row1 = query[0];
			col1 = query[1];
			row2 = query[2];
			col2 = query[3];
			diff[row1][col1] += 1;
			diff[row2 + 1][col1] -= 1;
			diff[row1][col2 + 1] -= 1;
			diff[row2 + 1][col2 + 1] += 1;
		}

		// Prefix sum + difference
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				x1 = i >= 1 ? mat[i - 1][j] : 0;
				x2 = j >= 1 ? mat[i][j - 1] : 0;
				x3 = i >= 1 && j >= 1 ? mat[i - 1][j - 1] : 0;
				mat[i][j] = diff[i][j] + x1 + x2 - x3;
			}
		}
		return mat;
	}
};