C++ | Segment Tree - Solution
Complexity\n- Time complexity: O(N * log(N))\n Add your time complexity here, e.g. O(n) \n\n- Space complexity: O(N)\n Add your space complexity here, e.g. O(n)
# Complexity\n- Time complexity: O(N * log(N))\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(N)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass SegmentTree {\nprivate:\n    vector<int> tree;\n    int n;\n\n    void build(int idx, int left, int right) {\n        if (left == right) {\n            tree[idx] = 1;\n        } else {\n            int mid = (left + right) / 2;\n            build(2 * idx + 1, left, mid);\n            build(2 * idx + 2, mid + 1, right);\n            tree[idx] = right - left + 1; // Initially, all positions are free\n        }\n    }\n\n    void update(int idx, int left, int right, int pos) {\n        if (left == right) {\n            tree[idx] = 0; // Position pos is now an obstacle\n        } else {\n            int mid = (left + right) / 2;\n            if (pos <= mid) {\n                update(2 * idx + 1, left, mid, pos);\n            } else {\n                update(2 * idx + 2, mid + 1, right, pos);\n            }\n            tree[idx] = max(tree[2 * idx + 1], tree[2 * idx + 2]);\n        }\n    }\n\n    int query(int idx, int left, int right, int ql, int qr) {\n        if (ql > qr) return 0;\n        if (left == ql && right == qr) {\n            return tree[idx];\n        }\n        int mid = (left + right) / 2;\n        return max(query(2 * idx + 1, left, mid, ql, min(qr, mid)),\n                   query(2 * idx + 2, mid + 1, right, max(ql, mid + 1), qr));\n    }\n\npublic:\n    SegmentTree(int size) {\n        n = size;\n        tree.resize(4 * n, 0);\n        build(0, 0, n);\n    }\n\n    void addObstacle(int pos) {\n        update(0, 0, n, pos);\n    }\n\n    bool canPlaceBlock(int x, int sz) {\n        int max_gap = query(0, 0, n, 0, x);\n        return (max_gap >= sz);\n    }\n};\n\nclass Solution {\npublic:\n    vector<bool> getResults(vector<vector<int>>& queries) {\n        vector<bool> ans;\n        int max_x = 0;\n\n        // Determine the maximum x to size the segment tree\n        for (const auto& q : queries) {\n            if (q[0] == 1 || q[0] == 2) {\n                max_x = max(max_x, q[1]);\n            }\n        }\n\n        SegmentTree segTree(max_x + 1);\n\n        for (auto q : queries) {\n            if (q[0] == 1) {\n                int x = q[1];\n                segTree.addObstacle(x);\n            } else if (q[0] == 2) {\n                int x = q[1];\n                int sz = q[2];\n                ans.push_back(segTree.canPlaceBlock(x, sz));\n            }\n        }\n\n        return ans;\n    }\n};\n```
['C++']