[C++] Segment Tree(array based), short and consice code with detailed step by step explantation.
Approach\n1. The obstacle can be placed between [0, 50000] .\n2. For the leaf node of the Segment Tree, we define seg[pos]=val as:\n    1. pos means the index o
# Approach\n1. The obstacle can be placed between `[0, 50000]` .\n2. For the leaf node of the Segment Tree, we define `seg[pos]=val` as:\n    1. `pos` means the **index of Segment Tree array**, also be the real **position on number line**.\n    2. `val` means the **max gap** between `[0, pos]`.\n    \n    Initially, the value for each `pos` is zero, this will not affect the result of the **query since we are taking the max gap**. \n    \n3. Every time we add a obstacle at `x` , we need to update 2 gap: `[l, x]` and `[x, r]`  where `l` and `r` are the obstacle  to the left and to the right of `x`.\n    \n    \u2192 update `pos=x` with a new gap size of `x-l` \n    \n    \u2192 update `pos=r` with a new gap size of `r-x` \n    \n4. For type 2 query, we need to find the max of gap from each `pos` between `[0, x]`  see if it can fit the `sz`.\n    \n    Also, we need to check another possible case: If `x` has no obstacle, then we find `l` (the obstacle to the left of `x` ) check if `x-l \u2265 sz` . This will happen when no update call on `pos\u2265x` before the query ,since we initialize all value to 0.\n\n# Complexity\n- Time complexity: $$O(q * \\log{n})$$\n<!-- Add your time complexity here, e.g.  -->\n- Space complexity: $$O(bound*4)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\n// since we taking the max for each query, we init all seg node with val 0, will not affet query.\n// now for every new obstacle added, we need to update 2 gap\nclass Solution {\npublic:\n    // 0-indexed\n    int bound = 50000;\n    int seg[50001*4] = {}; // Define seg[pos] = gap to left. if there is obstacles placed at `pos`. (x<=5e4)\n    void update(int uIdx, int newGap, int segIdx,  int l, int r) {\n        if(l==r) {\n            seg[segIdx] = newGap;\n            return;\n        }\n        int mid = (l+r)/2;\n        if(uIdx<=mid) update(uIdx, newGap, segIdx*2+1, l, mid);\n        else update(uIdx, newGap, segIdx*2+2, mid+1, r);\n        seg[segIdx] = max(seg[segIdx*2+1], seg[segIdx*2+2]);\n    }\n    int query(int ql, int qr, int segIdx, int l, int r) {\n        if(ql<=l && r<=qr) return seg[segIdx];\n        if(r<ql || qr<l) return 0;\n        int mid = (l+r)/2;\n        return max(query(ql, qr, segIdx*2+1, l, mid), query(ql, qr, segIdx*2+2, mid+1, r));\n    }\n    vector<bool> getResults(vector<vector<int>>& queries) {\n        set<int> obst{{0, bound}}; // obstacles\n        vector<bool> ans;\n        for(auto q: queries) {\n            if(q[0]==1) {\n                int x=q[1]; // add new obstacle to x.\n                auto it = obst.upper_bound(x); \n                int l = *prev(it), r=*it;\n                obst.insert(x);\n                update(x, x-l, 0, 0, bound);\n                update(r, r-x, 0, 0, bound);\n            }else {\n                int x=q[1], sz=q[2];\n                // 1. query the max gap can fit sz\n                if(query(0, x, 0, 0, bound) >= sz) {\n                    ans.push_back(true);\n                    continue;\n                }\n                // 2. check if x to previous obstacles can fit size.\n                auto it = obst.lower_bound(x); \n                ans.push_back(x-*prev(it) >=sz);\n            }\n        }\n        return ans;\n    }\n};\n```
['Segment Tree', 'C++']