Increment Submatrices by One Solution
Intuition\n Describe your first thoughts on how to solve this problem. \nInstead of incrementing each cell in the specified submatrix for every query, use a 2D 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nInstead of incrementing each cell in the specified submatrix for every query, **use a 2D difference array technique** to mark only the boundaries, then accumulate the changes in a final pass. This reduces the time complexity by limiting updates to just the submatrix boundaries.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Initialize a Difference Matrix:\n\n- Create an n x n matrix mat initialized to zero. This will serve as the difference matrix to handle range updates efficiently.\n\n2. Mark Boundaries for Each Query:\n\n- For each query [row1, col1, row2, col2], increment mat[row1][col1] by 1 to start adding 1 in the target submatrix.\n- If there\u2019s space beyond row2 and col2, decrement at the edges:\n- Decrement mat[row2 + 1][col1] (if within bounds) to stop incrementing downwards.\n- Decrement mat[row1][col2 + 1] (if within bounds) to stop incrementing rightward.\n- Add back mat[row2 + 1][col2 + 1] (if within bounds) to maintain the correct corners.\n\n3. Accumulate Results:\n\n- Perform a cumulative sum over mat row-wise and then column-wise to convert the difference matrix into the final matrix where each cell has the correct count of increments.\n\n4. Return the Matrix:\n\n- After both cumulative passes, mat will contain the final answer.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nTime Complexity: O(n\xB2 + q), where n\xB2 is for the cumulative sum calculation over the matrix, and q (number of queries) is for processing each query.\n\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nSpace Complexity: O(n\xB2) for storing the matrix.\n\n# Code\n```cpp []\n#include <vector>\n#include <iostream>\n\nclass Solution {\npublic:\n    std::vector<std::vector<int>> rangeAddQueries(int n, std::vector<std::vector<int>>& queries) {\n        // Initialize the n x n matrix with zeroes\n        std::vector<std::vector<int>> mat(n, std::vector<int>(n, 0));\n        \n        // Apply the difference approach for each query\n        for (const auto& query : queries) {\n            int row1 = query[0], col1 = query[1];\n            int row2 = query[2], col2 = query[3];\n            \n            mat[row1][col1] += 1; // Start adding from the top-left corner\n            if (row2 + 1 < n) mat[row2 + 1][col1] -= 1; // Stop adding below the bottom edge\n            if (col2 + 1 < n) mat[row1][col2 + 1] -= 1; // Stop adding to the right edge\n            if (row2 + 1 < n && col2 + 1 < n) mat[row2 + 1][col2 + 1] += 1; // Correct the overlap\n        }\n\n        // Calculate the final values using prefix sums\n        for (int i = 0; i < n; ++i) {\n            for (int j = 0; j < n; ++j) {\n                if (i > 0) mat[i][j] += mat[i - 1][j]; // Add the value from the top\n                if (j > 0) mat[i][j] += mat[i][j - 1]; // Add the value from the left\n                if (i > 0 && j > 0) mat[i][j] -= mat[i - 1][j - 1]; // Remove the overlap\n            }\n        }\n\n        return mat;\n    }\n};\n\n```
['C++']