Segment Tree Solution | | C++
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\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```cpp []\nclass SegmentTree {\nprivate:\n    vector<int> tree, lazy;\n    int n;\n\n    void propagate(int node, int start, int end) {\n        if (lazy[node] != 0) {\n            tree[node] += lazy[node];  // Apply the pending update\n\n            // If not a leaf node, propagate the laziness to the children\n            if (start != end) {\n                lazy[2 * node + 1] += lazy[node]; // Left child\n                lazy[2 * node + 2] += lazy[node]; // Right child\n            }\n\n            // Clear the lazy value for the current node\n            lazy[node] = 0;\n        }\n    }\n\n    void build(const vector<int>& arr, int node, int start, int end) {\n        if (start == end) {\n            tree[node] = arr[start];\n        } else {\n            int mid = start + (end - start) / 2;\n            int leftChild = 2 * node + 1;\n            int rightChild = 2 * node + 2;\n            build(arr, leftChild, start, mid);\n            build(arr, rightChild, mid + 1, end);\n            tree[node] = max(tree[leftChild], tree[rightChild]);\n        }\n    }\n\n    int query(int node, int start, int end, int l, int r) {\n        propagate(node, start, end);  // Apply any pending updates\n\n        if (r < start || end < l) {\n            return INT_MIN;\n        }\n        if (l <= start && end <= r) {\n            return tree[node];\n        }\n\n        int mid = start + (end - start) / 2;\n        int leftChild = 2 * node + 1;\n        int rightChild = 2 * node + 2;\n        int leftMin = query(leftChild, start, mid, l, r);\n        int rightMin = query(rightChild, mid + 1, end, l, r);\n        return max(leftMin, rightMin);\n    }\n\n    void update(int node, int start, int end, int l, int r, int value) {\n        propagate(node, start, end);  // Apply any pending updates\n\n        if (r < start || end < l) {\n            return;\n        }\n        if (l <= start && end <= r) {\n            tree[node] += value;\n            if (start != end) {\n                lazy[2 * node + 1] += value;  // Mark left child for update\n                lazy[2 * node + 2] += value;  // Mark right child for update\n            }\n            return;\n        }\n\n        int mid = start + (end - start) / 2;\n        int leftChild = 2 * node + 1;\n        int rightChild = 2 * node + 2;\n        update(leftChild, start, mid, l, r, value);\n        update(rightChild, mid + 1, end, l, r, value);\n        tree[node] = max(tree[leftChild], tree[rightChild]);\n    }\n\npublic:\n    SegmentTree(const vector<int>& arr) {\n        n = arr.size();\n        tree.resize(4 * n, INT_MIN);\n        lazy.resize(4 * n, 0);  // Initialize the lazy array with 0\n        build(arr, 0, 0, n - 1);\n    }\n\n    int query(int l, int r) {\n        return query(0, 0, n - 1, l, r);\n    }\n\n    void update(int l, int r, int value) {\n        update(0, 0, n - 1, l, r, value);\n    }\n};\n\nclass Solution {\npublic:\n    int maxRemoval(vector<int>& nums, vector<vector<int>>& q) {\n        int n = nums.size();\n        int m = q.size();\n\n        vector<int> prefixSum(n + 1, 0);\n        for (int i = 0; i < m; ++i) {\n            int l = q[i][0], r = q[i][1];\n            prefixSum[l] -= 1;\n            prefixSum[r + 1] += 1;\n        }\n\n        int current = 0;\n        for (int i = 0; i < n; ++i) {\n            current += prefixSum[i];\n            nums[i] += current;\n            if (nums[i] > 0) return -1;\n        }\n\n        SegmentTree segTree(nums);\n        int removableCount = 0;\n        sort(q.begin(), q.end(), [](auto a, auto b) {\n            return a[1] - a[0] == b[1] - b[0] ? a[0] == b[0] ? a[1] < b[1] : a[0] < b[0] : a[1] - a[0] < b[1] - b[0];\n        });\n\n        for (const auto& query : q) {\n            int l = query[0], r = query[1];\n            if (segTree.query(l, r) < 0) {\n                ++removableCount;\n                segTree.update(l, r, 1);  // Remove the query by updating the range\n            }\n        }\n\n        return removableCount;\n    }\n};\n```
['Segment Tree', 'C++']