C++ Sum of Matrix After Queries
Intuition\nThe key observation here is that applying updates to rows or columns repeatedly may result in unnecessary recalculations if we go from the beginning 
# Intuition\nThe key observation here is that applying updates to rows or columns repeatedly may result in unnecessary recalculations if we go from the beginning of the query list. Hence, a **reverse** approach is optimal: we apply updates from the last query to the first. This way, we can skip any redundant operations (i.e., if a row or column has already been updated by a later query).\n\n# Approach\n**1. Understanding the Query Types:**\n  - There are two types of queries:\n    - **Type 0:** Update all elements in a row with a specific value.\n    - **Type 1:** Update all elements in a column with a specific value.\n  \nWe need to compute the total matrix sum after processing all the queries.\n\n**2. Reverse Processing:**\n\n- Since **later** queries **overwrite** earlier ones (i.e., if a row is updated twice, only the **last** **update** matters), we process the queries from the end of the list to the beginning.\n\n**3. Tracking Visited Rows and Columns:**\n\n- To avoid recalculating sums for rows or columns that have already been updated, we maintain two boolean vectors:\n  - **rowvis**: Tracks whether a row has already been updated.\n  - **colvis**: Tracks whether a column has already been updated.\n- We also maintain counters (**rowcount** and **colcount**) to keep track of how many **unique** rows and columns have been updated.\n\n**4. Calculating the Result:**\n\n- For each query, depending on whether it is a row update (type **0**) or a column update (type **1**):\n  - If the row (for type 0) or column (for type 1) has not been updated before, we calculate the contribution to the matrix sum.\n  - For a row update (type 0), each element in the row contributes **colcount** ```n\u2212colcount```, which is the number of columns that haven\'t been updated.\n  - For a column update (type 1), each element in the column contributes **rowcount** ```n\u2212rowcount```, which is the number of rows that haven\'t been updated.\n  - After processing the query, we mark the respective row or column as **visited** and update the **count**.\n\n# Complexity\n- **Time complexity:**\n**O(q)**, where q is the number of queries. We process each query once in reverse, and each query takes constant time.\n\n- **Space complexity:**\n**O(n)**, where **n** is the size of the matrix. We use two vectors **rowvis** and **colvis** of size **n** to track which rows and columns have been updated.\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    long long matrixSumQueries(int n, vector<vector<int>>& queries) {\n        int q = queries.size(); // Number of queries\n        \n        // Arrays to track which rows and columns have already been updated\n        vector<int> rowvis(n, 0), colvis(n, 0);\n        \n        int rowcount = 0, colcount = 0; // Counts for unique row and column updates\n        long long result = 0; // Variable to store the final matrix sum\n        \n        // Traverse the queries from the last to the first\n        for(int i = q - 1; i >= 0; i--) {\n            int type = queries[i][0]; // Type of query (0 for row, 1 for column)\n            int idx = queries[i][1];  // Row or column index\n            int val = queries[i][2];  // Value to update\n            \n            if(type == 0) { // Row update\n                if(rowvis[idx] == 0) { // If this row hasn\'t been updated yet\n                    rowvis[idx] = 1; // Mark the row as updated\n                    result += 1ll * (n - colcount) * val; // Add the sum contribution from this row\n                    rowcount++; // Increment the count of updated rows\n                }\n            } else { // Column update\n                if(colvis[idx] == 0) { // If this column hasn\'t been updated yet\n                    colvis[idx] = 1; // Mark the column as updated\n                    result += 1ll * (n - rowcount) * val; // Add the sum contribution from this column\n                    colcount++; // Increment the count of updated columns\n                }\n            }\n        }\n        \n        return result; // Return the total matrix sum after all queries\n    }\n};\n```
['Array', 'Hash Table', 'Math', 'C++']