Prefix Sum| Python
Approach\n- Assume there is one row only [0,0,0,0,0]. Now if I want to add value 2 at index 2,3 only, I will add 2 on index 2 and subtract 2 from index 4. In th
# Approach\n- Assume there is one row only [0,0,0,0,0]. Now if I want to add value 2 at index 2,3 only, I will add 2 on index 2 and subtract 2 from index 4. In this way, when we will calculate prefix sum, 2 will be added on indices 2,3.\n- [0,0,2,0,-2]\n- Now find prefix sum:\n- [0,0,2,2,0]\n- We can extend the same idea in 2D matrix.\n\n# Complexity\n- Time complexity:\n$$O(n^2)$$\n\n- Space complexity:\n$$O(1)$$ if we do not consider returned matrix space\n\n# Code\n```python3 []\nclass Solution:\n    def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:\n        matrix = [[0]*n for i in range(n)]\n        # add 1 to every row\'s row1,col1 position and -1 to every row\'s r,col2+1 position\n        for row1,col1,row2,col2 in queries:\n            for r in range(row1,row2+1):\n                matrix[r][col1]+=1\n                if col2+1 <n:\n                    matrix[r][col2+1]-=1\n        # calculate prefix sum now\n        for i in range(n):\n            row = matrix[i]\n            for j in range(1,n):\n                row[j] = row[j]+row[j-1]\n\n        return matrix\n```
['Python3']