Explained using Prefix-Sum & Difference-Array
Intuition\n Describe your first thoughts on how to solve this problem. \nThis uses prefix-sum & difference-array, but on a matrix.\n\n# Approach\n Describe your
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThis uses prefix-sum & difference-array, but on a matrix.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nIf the range is from (i, j) to (x, y), then if we only increment mat[i][j] by 1, and use prefix sum for matrix, it will propagate through the rest of the matrix.\n\nNow we want to stop at (x, y). So we can decrement 1 from (x + 1, j) and (i, y + 1) and since we are using prefix sum, it will propagate through the (x + 1) row and (y + 1) col and the next values will not be effected by the current range.\n\nAlso, since we are decrementing both (x + 1, j) and (i, y + 1), we have incrementing (x + 1, y + 1) as otherwise it will decremented twice.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(n^2)\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(n^2)\n\n# Code\n```\nclass Solution {\npublic:\n    vector<vector<int>> rangeAddQueries(int n, vector<vector<int>>& queries) {\n        vector<vector<int>> arr(n, vector<int>(n, 0));\n\n        for(auto& i : queries){\n            int a = i[0], b = i[1], x = i[2], y = i[3];\n            arr[a][b]++;\n\n            if(x + 1 < n)arr[x + 1][b]--;\n            if(y + 1 < n)arr[a][y + 1]--;\n            if(x + 1 < n && y + 1 < n)arr[x + 1][y + 1]++;\n        }\n\n        for(int i = 0; i < n; i++){\n            for(int j = 0; j < n; j++){\n                int prevRow = i - 1 >= 0 ? arr[i - 1][j] : 0;\n                int prevCol = j - 1 >= 0 ? arr[i][j - 1] : 0;\n                int prevDiag = (i - 1 >= 0 && j - 1 >= 0) ? arr[i - 1][j - 1] : 0;\n\n                arr[i][j] = prevRow + prevCol - prevDiag + arr[i][j];\n            }\n        }\n\n        return arr;\n    }\n};\n```
['C++']