Simple 4 step || Prefix Sum || C++ Solution || Optimized approach
Intuition\nApply prefix sum on 2D Matrix. \n\nStep 1 : arr[x1][y1]++\nStep 2 : arr[x2+1][y2+1]++\nstep 3 : arr[x2+1][y1]--\nstep 4 : arr[x1][y2+1]--\n\nAfter pe
# Intuition\nApply prefix sum on 2D Matrix. \n\nStep 1 : arr[x1][y1]++\nStep 2 : arr[x2+1][y2+1]++\nstep 3 : arr[x2+1][y1]--\nstep 4 : arr[x1][y2+1]--\n\nAfter performing all the queries\n\narr[i][j] += arr[i - 1][j] + arr[i][j - 1] - arr[i - 1][j - 1];\n\n# Complexity\n- Time complexity: O(NXN)\n\n- Space complexity: O(NXN)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    vector<vector<int>> rangeAddQueries(int n, vector<vector<int>>& q) \n    {\n        vector<vector<int>>arr(n, vector<int>(n, 0));\n        \n        for(int i=0; i<q.size(); i++)\n        {\n            int x1 = q[i][0];\n            int y1 = q[i][1];\n            int x2 = q[i][2];\n            int y2 = q[i][3];\n            \n            arr[x1][y1]++;\n            if(y2+1<n && x2+1<n) arr[x2 + 1][y2 + 1]++;\n            if(y2+1 < n) arr[x1][y2 + 1]--;\n            if(x2+1 < n) arr[x2 + 1][y1]--;\n            \n        }\n        \n\t\tfor(int i=0;i<n;i++)\n        {\n            for (int j = 0; j < n; j++) {\n                \n                if(i-1 >= 0) arr[i][j] += arr[i-1][j];\n                if(j-1 >= 0) arr[i][j] += arr[i][j-1];\n                if(i-1>=0 && j-1>=0) arr[i][j] -= arr[i-1][j-1];\n            }\n        }\n\t\t\n        \n        return arr;\n    }\n};\n```
['Matrix', 'Prefix Sum', 'Python', 'C++', 'Java']