single query Fenwick tree
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```\nclass Solution {\npublic:\n    int n;\n    vector<int>bit;\n    void ft(vector<vector<int>>& queries){\n        int x=min(5*10000,(3*(int)queries.size()));\n        n=x;\n        bit=vector<int>(n+2,0);\n    }\n    void add(int id,int val){\n        while(id<=n){\n            bit[id]=max(bit[id],val);\n            id+=(id&-id);\n        }\n    }\n    int query(int id){\n        int ans=0;\n        while(id>0){\n            ans=max(bit[id],ans);\n            id-=(id&-id);\n        }\n        return ans;\n    }\n    vector<bool> getResults(vector<vector<int>>& queries) {\n        vector<bool>ans;\n        ft(queries);\n        set<int>ob;\n        //build all obstacle\n        ob.insert(0);\n        ob.insert(n+1);\n        for(auto q:queries){\n            if(q[0]==1){\n                ob.insert(q[1]);\n            }\n        }\n        for(auto it=ob.begin();it!=ob.end();it++){\n            if(it==ob.begin())continue;\n            auto p=prev(it);\n            int x=*it;\n            add(x,x-*p);\n        }\n        for(int i=queries.size()-1;i>=0;i--){\n            if(queries[i][0]==1){\n                int x=queries[i][1];\n                auto it=ob.find(x);\n                auto prv=prev(it);\n                auto nxt=next(it);\n                ob.erase(it);\n                add(*nxt,*nxt-*prv);\n            }else{\n                int x=queries[i][1];\n                int sz=queries[i][2];\n                auto nxt=ob.upper_bound(x);\n                auto prv=prev(nxt);\n                int maxgap=max(query(*prv),x-*prv);\n                ans.push_back(maxgap>=sz);\n            }\n        }\n        reverse(ans.begin(),ans.end());\n        return ans;\n    }\n};\n```
['C++']