[Python3] | Intuition behind scanline explained with pictures
Bruteforce\nFor each query we would travel in the range and make the increments. According to the given constrains where n can be 500, meaning the matrix size c
# Bruteforce\nFor each query we would travel in the range and make the increments. According to the given constrains where n can be 500, meaning the matrix size can be $$N = n^2 = 250000$$ and queries can be as big as $$M = 10^4$$, so in worst case we have complexity of $$O(N*M) = 25 * 10^8$$ which will give us TLE.\n\n# Optimization\nInstead of adding 1 to every cell in the given range, we can mark cells with `+1` from where the **range starts** and `-1` in the **next cell of where the range ends** for every row. \n\nThat means we traverse each row `x`, and mark ($$r_x$$,$$c_1$$) with `+1` and mark ($$r_x$$,$$c_2+1$$) with `-1`. If $$c_2+1$$ is not less than `n` then mark ($$r_x+1,0$$) i.e first column of next row with `-1`. If $$r_x+1$$ is also not less than `n` then need not do anything.\n\n![image.png](https://assets.leetcode.com/users/images/cd402701-be2d-4192-8cf9-ed86fd10092b_1673768057.2343714.png)\n\nNow we start with `cur_sum` as 0 and add value at each cell to `cur_sum` and assign it\'s value to the cell.\n\n![image.png](https://assets.leetcode.com/users/images/e4332c7f-7916-4d4c-ae50-5003693f7eaf_1673769683.8757432.png)\n\n\n\n# If this was at all helpful, please do upvote : )\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        \n        for r1,c1,r2,c2 in queries:\n            for r in range(r1,r2+1):\n                mat[r][c1] += 1\n                if c2+1<n: mat[r][c2+1] -= 1\n                elif r+1<n: mat[r+1][0] -= 1\n        \n        cur_sum = 0\n        for i in range(n):\n            for j in range(n):\n                cur_sum += mat[i][j]\n                mat[i][j] = cur_sum\n        \n        return mat\n\n```
['Prefix Sum', 'C++', 'Python3']