Easy explanation (segment tree) CPP
Explanation\nWe have an array nums and a list of queries in the form of [Left, Right]. Each query allows us to decrement the elements of nums in the range [Left
# Explanation\nWe have an array nums and a list of queries in the form of [Left, Right]. Each query allows us to decrement the elements of nums in the range [Left, Right] by 1. The goal is to determine the minimum number of queries required to make all elements in nums less than or equal to 0.\n\n\n# Intuition\n**1. Sorting the Queries**:\nIf we sort the queries based on Left, our greedy choice would be to select the query with the longest range (i.e., the maximum Right) that can affect the current index.\n\n**2. Valid Queries:**\nFor an element nums[n], only queries with Left \u2264 n and Right >= n can modify its value.\n# Approach\n**1. Using a Segment Tree:**\n\n- Create a segment tree to store the values of nums in its leaf nodes.\nImplement two additional functions:\n- One to decrement a range [L, R].\nAnother to fetch the current value of nums at any index after applying all modifications.\n\n**2. Sorting the Queries:**\n\nSort the queries first by Left in ascending order.\nFor queries with the same Left, sort them by Right in descending order.\n\n**3. Processing Each Index:**\n\nFor each index i in nums:\nPush the Right values of all queries where Left \u2264 i into a priority queue (max-heap).\nThe priority queue ensures that the query with the maximum range (Right) is processed first, providing maximum coverage.\n\n**4. Decrementing the Value:**\n\nWhile nums[i] > 0, repeatedly pop the top element of the priority queue and use the corresponding query to decrement nums[i].\nUpdate the range [i, Right] in the segment tree.\n\n**5. Edge Cases:**\n\nIf the priority queue becomes empty and nums[i] > 0, it is impossible to decrement the value further, so return -1.\n\n**6. Result Calculation:**\n\nCount the number of queries used and return queries.size() - count as the final result.\n# Complexity\n**Time Complexity:**\n\n**Sorting queries :** O(qlogq), where q is the number of queries.\n**Maintaining the priority queue:** O(nlogq), as each index can push and pop elements.\n**Segment tree operations:**(build and update): \uD835\uDC42(\uD835\uDC5Blog \uD835\uDC5B).\n**Overall complexity:** \uD835\uDC42((\uD835\uDC5B+\uD835\uDC5E)log max(n,q)).\n\n**Space Complexity:**\n\n**Segment tree:** O(n).\n**Priority queue:** O(q).\n**Total:** O(n+q).\n# Code\n```cpp []\nclass ST { // Segment tree class\npublic:\n    vector<int> tree;\n    vector<int> ltree; // Lazy tree for lazy propagation\n\n    ST(int n) {\n        tree.resize(4 * n);\n        ltree.resize(4 * n, 0);\n    }\n\n    void build(int ind, int left, int right, vector<int>& nums) {\n        if (left == right) {\n            tree[ind] = nums[left]; // Leaf node stores nums[i]\n            return;\n        }\n        int mid = (left + right) / 2;\n        build(2 * ind + 1, left, mid, nums); // Recursive call\n        build(2 * ind + 2, mid + 1, right, nums);\n        tree[ind] = max(tree[2 * ind + 1], tree[2 * ind + 2]);\n    }\n\n    void propagate(int ind, int left, int right) { // Lazy propagation\n        if (ltree[ind] != 0) {\n            tree[ind] -= ltree[ind];\n            if (left != right) {\n                ltree[2 * ind + 1] += ltree[ind];\n                ltree[2 * ind + 2] += ltree[ind];\n            }\n            ltree[ind] = 0;\n        }\n    }\n\n    void operation(int ind, int left, int right, int L, int R, int val) { // Update range [L, R]\n        propagate(ind, left, right);\n        if (R < left || L > right) return;\n        if (L <= left && right <= R) {\n            tree[ind] -= val;\n            if (left != right) {\n                ltree[2 * ind + 1] += val;\n                ltree[2 * ind + 2] += val;\n            }\n            return;\n        }\n        int mid = (left + right) / 2;\n        operation(2 * ind + 1, left, mid, L, R, val);\n        operation(2 * ind + 2, mid + 1, right, L, R, val);\n        tree[ind] = max(tree[2 * ind + 1], tree[2 * ind + 2]);\n    }\n\n    int value(int ind, int left, int right, int val) { // Get updated value at index val\n        propagate(ind, left, right);\n        if (val < left || val > right) return INT_MAX;\n        if (left == right) return tree[ind];\n        int mid = (left + right) / 2;\n        return min(value(2 * ind + 1, left, mid, val), value(2 * ind + 2, mid + 1, right, val));\n    }\n};\n\nclass Solution {\npublic:\n    static bool comp(const vector<int>& a, const vector<int>& b) {\n        if (a[0] != b[0]) return a[0] < b[0];\n        return a[1] > b[1];\n    }\n\n    int maxRemoval(vector<int>& nums, vector<vector<int>>& q) {\n        sort(q.begin(), q.end(), comp); // Sort queries\n        priority_queue<int> pq; // Store the right-most value of queries\n        int n = nums.size();\n        ST st(n);\n        st.build(0, 0, n - 1, nums);\n\n        int count = 0, pushed = -1; // Count of queries used, index of last pushed query\n        for (int i = 0; i < n; i++) {\n            for (int j = pushed + 1; j < q.size(); j++) {\n                if (q[j][0] != i) break;\n                pq.push(q[j][1]);\n                pushed = j;\n            }\n            while (st.value(0, 0, n - 1, i) > 0) { // Decrement until nums[i] \u2264 0\n                if (pq.empty() || pq.top() < i) return -1;\n                int end = pq.top();\n                pq.pop();\n                count++;\n                st.operation(0, 0, n - 1, i, end, 1); // Update range [i, end]\n            }\n        }\n\n        return q.size() - count;\n    }\n};\n\n\n```
['Greedy', 'Segment Tree', 'Recursion', 'Heap (Priority Queue)', 'C++']