[Python] Range Caching
Intuition\nBased on this solution [Python3] Sweep Line (Range Addition w/ Visualization), Clean & Concise. I\'ll write some explanation for the 2-D range cachin
# Intuition\nBased on this solution [[Python3] Sweep Line (Range Addition w/ Visualization), Clean & Concise](https://leetcode.com/problems/increment-submatrices-by-one/solutions/3052675/python3-sweep-line-range-addition-w-visualization-clean-concise/). I\'ll write some explanation for the 2-D range caching for personal record.\n\nObservation: if the caching and restoration works for a single query, it will work for any amount of queries.\nProof: we can conduct the caching and restoration on separate matrixs and sum them up, due to the properties of addition, this won\'t change the result.\n\nThus we just need to proof that this method works for a single query. If we want to step backwards, that\'s we want to restore the cache vertically, then what we want is something like below:\n\n1   1   1   1\n0   0   0   0\n0   0   0   0\n-1  -1   -1  -1\n\nIf we sweep all the columns, we\'ll get the result of a single query.\n\nThis can be further cached horizontally like this:\n1 0 0 0 -1\n0 0 0 0 0\n0 0 0 0 0\n-1 0 0 0 1\n\nbacause 1 0 0 0 -1 -> 1   1   1   1 and -1 0 0 0 1 -> -1 -1 -1 -1 if we sweep the row.\n\nThus, if we add 1 to `mat[r1][c1]` and `mat[r2 + 1][c2 + 1]` and minus 1 to `mat[r2 + 1][c1]` and `mat[r1][c2 + 1]`, after sweeping vertically and horizontally, we\'ll get the resul tof a single query.\n# Complexity\n- Time complexity:\n$$O(n^2 + q)$$\n\n- Space complexity:\n$$O(1)$$\n\n# Code\n```\nclass Solution:\n    def rangeAddQueries(self, n: int, queries: List[List[int]]):\n        mat = [[0 for _ in range(n)] for _ in range(n)]\n        for r1, c1, r2, c2 in queries:\n            mat[r1][c1] += 1\n            if r2 + 1 < n:\n                mat[r2 + 1][c1] -= 1 \n            if c2 + 1 < n:\n                mat[r1][c2 + 1] -= 1\n            if r2 + 1 < n and c2 + 1 < n:\n                mat[r2 + 1][c2 + 1] += 1\n        for i in range(n):\n            for j in range(1, n):\n                mat[i][j] += mat[i][j - 1]\n        for j in range(n):\n            for i in range(1, n):\n                mat[i][j] += mat[i - 1][j]\n        return mat\n```
['Python3']