Python3 | Prefix-Sum-Difference Array- Accepted Solutions
Intuition\n Describe your first thoughts on how to solve this problem. \nUsing the difference array to solve the problem\n# Approach\nThe method is applying pre
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nUsing the difference array to solve the problem\n# Approach\nThe method is applying prefix sum to each row. we only need to mark the start and end position\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ --> \n    O(N * N), because we are going through the entire matrix at the end\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n    O(1) if we do not count the output size\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 row1, col1, row2, col2 in queries:\n            for r in range(row1, row2 + 1):\n                mat[r][col1] += 1\n                if col2 + 1 < n:\n                    mat[r][col2 + 1] -= 1\n        for r in mat:\n            for i in range(1, len(r)):\n                r[i] += r[i - 1]\n        return mat\n            \n        \n```
['Prefix Sum', 'Python3']