C++ and Python 70% Faster Code | Prefix Sum | Range Caching Behaviour
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\nPrefix Sum\n Describe your approach to solving the problem. \n\n# Complex
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\nPrefix Sum\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n**C++ Solution:-**\n```\nclass Solution {\npublic:\n    vector<vector<int>> rangeAddQueries(int n, vector<vector<int>>& queries) {\n        vector<vector<int>> mat(n, vector<int>(n,0));\n        for(auto &it:queries) {\n            int r1 = it[0];\n            int c1 = it[1];\n            int r2 = it[2];\n            int c2 = it[3];\n            for(int i=r1; i<=r2; i++) {\n                mat[i][c1] += 1;\n                if(c2+1<n) mat[i][c2+1] -= 1;\n            }\n        }\n        for(int r=0; r<n; r++) {\n            for(int c=1; c<n; c++) {\n                mat[r][c] += mat[r][c-1];\n            }\n        }\n        return mat;\n    }\n};\n```\n**Python Solution:-**\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            for r in range(r1, r2+1):\n                mat[r][c1] += 1\n                if c2+1 < n:\n                    mat[r][c2+1] -= 1\n        for row in range(n):\n            for col in range(1, n):\n                mat[row][col] += mat[row][col-1]\n        return mat\n```
['Prefix Sum', 'C++', 'Python3']