C++ Difference Matrix (inspired by the difference array)
Intuition\nThis solution is derived from the idea of the 1-d difference array. \nFor an 1d array, if there are multiple update before a query(note here that the
# Intuition\nThis solution is derived from the idea of the 1-d difference array. \nFor an 1d array, if there are multiple update before a query(note here that the question\'s wording is vague -- update in this question is "query," but query means to assess the value of the array), we can do the following:\n\ncreate a difference array $diff$ such that $diff[i] = arr[i] - arr[i-1]$. To update a given range $(i,j)$ by some value $c$, simply update as \n`diff[i] += c` and `diff[j+1] -= c`. Then we reaseemble the prefix sum of the difference array to get the result, i.e., \n`arr_final[i] = arr_final[i-1] + diff[i]`. \n\nThis can be generalized to 2d by choosing the prefix sum very carefully.  \n\n\n# Complexity\n- Time complexity: $O(n^2)$, each insert takes $O(1)$ and the number of queries is strictly bounded by the size of the matrix. The building and the rebuilding take both $O(n)$\n- Space complexity:$O(n^2)$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\n\nusing namespace std;\nclass Solution {\npublic:\n    vector<vector<int>> rangeAddQueries(int n, vector<vector<int>>& queries) {\n\n        // create difference matrices    \n        vector<vector<int>> diff_matrix;\n        vector<vector<int>> result_matrix;\n        for (int i = 0; i < n; i ++) {\n            vector<int> current(n, 0);\n            vector<int> current_result(n, 0);\n            diff_matrix.push_back(current);\n            result_matrix.push_back(current_result);\n        }\n        int x1, y1, x2, y2;\n        for (auto vect : queries) {\n            int x1 = vect[0], y1 = vect[1], x2 = vect[2], y2 = vect[3];\n            insert(diff_matrix, x1, y1, x2, y2, 1);\n        }\n        //reassemble the matrix \n        \n        for (int i = 0; i < n; i ++) {\n            for (int j = 0; j < n; j ++) {\n                int up_left = (i-1 >= 0 && j - 1 >=0) ? result_matrix[i-1][j-1] : 0;\n                int up = (i - 1 >= 0) ? result_matrix[i-1][j] : 0; \n                int left = (j - 1 >= 0) ? result_matrix[i][j-1] : 0;\n                result_matrix[i][j] = diff_matrix[i][j] - up_left + up + left;\n            }\n        }\n        return result_matrix;\n        // for each query, we perform the following:\n        // \n    }\n    void insert(vector<vector<int>>& diff_matrix, int x1, int y1, int x2, int y2, int update){\n        diff_matrix[x1][y1] += update;\n        if (x2 + 1 < diff_matrix.size())\n            diff_matrix[x2 + 1][y1] -= update;\n        if (y2 + 1 < diff_matrix[0].size())\n            diff_matrix[x1][y2 + 1] -= update;\n        if (x2 + 1 < diff_matrix[0].size() && y2 + 1 < diff_matrix.size())\n            diff_matrix[x2 + 1][y2 + 1] += update;\n    }\n};\n\n```
['C++']