[Python3] Difference Array | Postfix Sum
The strategy is to keep track of the changes made to each cell at the boundaries, instead of maintaining the final value of each cell.\n\nInitially, we initiali
The strategy is to keep track of the changes made to each cell at the boundaries, instead of maintaining the final value of each cell.\n\nInitially, we initialize the matrix with all zeroes. For each query, we add 1 to the top-left corner cell ($r_{start}, c_{start}$) and subtract 1 from the cells at ($r_{start}, c_{end+1}$) and ($r_{end+1}, c_{start}$). However, in the nature of prefix computation, this leads to a duplicate cost by subtracting both row and column boundaries. Therefore, we balance this out by adding 1 to the cell after the bottom-right corner of the sub-matrix ($r_{end+1}, c_{end+1}$). Afterwards, we use the prefix sum technique to update the final matrix by adding the differences from the previous cells.\n\nThis approach enables us to update the matrix in constant time for each query, without the need to iterate through the entire matrix for each query.\n\n# Complexity\nTime `O(q+n^2)`\nSpace `O(1)`\n\n# Code\n```\nclass Solution:\n    def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:\n        mat = [[0]*n for _ in range(n)]\n        for r1, c1, r2, c2 in queries:\n            mat[r1][c1] += 1\n            if r2 < n-1:\n                mat[r2+1][c1] -= 1\n            if c2 < n-1:\n                mat[r1][c2+1] -= 1\n            if r2 < n-1 and c2 < n-1:\n                mat[r2+1][c2+1] += 1\n        for i in range(1, n):\n            mat[0][i] += mat[0][i-1]\n            mat[i][0] += mat[i-1][0]\n        for i in range(1, n):\n            for j in range(1, n):\n                mat[i][j] = mat[i][j] + mat[i-1][j] + mat[i][j-1] - mat[i-1][j-1]\n        return mat\n```
['Python3']