LeetCode Daily Problem P2536: Add 1 to Submatrix Elements

---

Timeline

Timeline

2025-11-14

init

Difference and prefix sum are inverse operations

---

Problem:

P2536 Submatrix element addition 1

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

This is a template problem for difference matrices, which can be generalized to adding other integers to a submatrix, not limited to +1. An O(1) operation on the difference matrix can leave traces of adding +1 to the submatrix, and then, based on 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 submatrix from (0,0) to (i,j).

Note the size of the difference matrix! It must be one row and one column larger than the original matrix.

#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;
	}
};