C++ AC - Difference Array for 2D Array✅✅
Intuition\n Describe your first thoughts on how to solve this problem. \nWe need to calculate the changes after performing the queries . A brute force solution 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nWe need to calculate the changes after performing the queries . A brute force solution will be traversing the 2D vector for each query and updating the matrix for the given range of query . But this repeated work can be avoided by calculating the amount of increment for each cell.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nI will try to mark each row in such a way that it will signify the range in which changes can be done\n\nFor ex --  We are given an array of size 4 \n0 0 0 0\n\nquery 1 --- increase the array range 1 to 3 by 1.\n\n0 1 1 1 \n\nquery 2 --- increase the array range  2 to 3 by 1\n\n0 1 2 2\n\nBut it will take so much time to update again and again. It will not be sufficient to get **AC**\n\nSo instead of updating each time , Lets mark range start as +1 and end+1 as -1. \n\nTake an array of n+1 size to avoid out of bound error\n0 0 0 0 0\n\nafter query 1 (increase 1 to 3) i.e increase  index 1 by 1 and decrease  index 3+1 => 4 by 1\n\n0 1 0 0 -1 \n\nafter query 2 (increase 2 to 3) i.e increase  index 2 by 1 and decrease 1 index 3+1=>4 by 1\n\n0 1 1 0 -2 \n\nNow generate the **prefix sum** of our difference array.\n\n0 1 2 2 0\n\nClearly the result of both approaches  are same but in this method we have done **query updation in constant time** and at last prefix sum takes linear time which is better than traversing the array again and again.\n\nThis same concept of difference array we can use for 2D array just traverse rows \nfor( row -- start to row -- end)\n{\n      // do same as above inside the loop for each row\n}  \n\nAt last generate the answer 2D array by taking prefix sum of each row.Below is given the code\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```\nclass Solution {\npublic:\n    vector<vector<int>> rangeAddQueries(int n, vector<vector<int>>& queries) {\n        \n        vector<vector<int>>ans(n,vector<int>(n,0));\n\n        // row size n column size n+1\n        vector<vector<int>>diff(n,vector<int>(n+1,0));\n        // I will use the concept of difference array for row \n\n        // i will take the row wise prefix sum of the difference array and assign it back to our ans 2d array \n\n        for(int i = 0 ; i < queries.size() ; i++)\n        {\n            // for every row \n            // increase the \n            // start by 1 and decrease the end+1 by 1\n            \n\n             int rstart = queries[i][0];\n             int cstart = queries[i][1];\n             int rend   = queries[i][2];\n             int cend   = queries[i][3];\n\n             for( int j = rstart ; j <= rend ; j++)\n             {\n                  diff[j][cstart]+=1;\n                  diff[j][cend+1]-=1;\n             } \n\n        }\n        \n        // now take prefix sum of every row of difference matrix\n\n        for(int i = 0 ; i < n ; i++)\n        {\n            for(int j = 0 ; j < n ;j++)\n            {\n                 if(j > 0)\n                 {\n                     diff[i][j]+=diff[i][j-1];\n                 }\n\n                 // assign the value at each cell after calculating   the prefix sum till that cell \n\n                 ans[i][j]=diff[i][j];\n            }\n        }\n\n        return ans;\n    }\n};\n```
['Prefix Sum', 'C++']