Python | Segment Tree solution | faster than 100% | Best Solution
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```\nfrom copy import deepcopy\nclass Node:\n    def __init__(self, flag = True, node = None):\n        if flag:\n            self.left = None\n            self.right = None\n            self.lval = 0\n            self.rval = 0\n            self.bestval = 0\n            self.connected = True\n        else:\n            self.left = node.left\n            self.right = node.right\n            self.lval = node.lval\n            self.rval = node.rval\n            self.bestval = node.bestval\n            self.connected = node.connected\n        \ndef Build(l,r, arr):\n    if l == r:\n        return Node()\n    mid = (l+r)//2\n    lnode = Build(l, mid, arr)\n    rnode = Build(mid+1, r, arr)\n    node = Node()\n    node.left = lnode\n    node.right = rnode\n    node.bestval = lnode.bestval + rnode.bestval+1\n    node.lval = node.bestval\n    node.rval = node.bestval\n    return node\n\ndef update(l,r,idx, node):\n    if l > r:\n        return\n    mid = (l+r)//2\n    if l == r == idx:\n        node.connected = False\n        node.lval = 0\n        node.rval = 0\n        node.bestval = 0\n        return \n    if l <= idx <= mid:\n        update(l,mid, idx, node.left)\n    elif mid+1 <= idx <= r:\n        update(mid+1, r, idx, node.right)\n    else:\n        return\n    lnode = node.left\n    rnode = node.right\n    if lnode.connected and rnode.connected:\n        node.bestval = lnode.bestval + rnode.bestval+1\n        node.lval = node.bestval\n        node.rval = node.bestval\n    elif lnode.connected:\n        node.bestval = max(lnode.bestval + rnode.lval+1, rnode.bestval)\n        node.lval = lnode.bestval + rnode.lval+1\n        node.rval = rnode.rval\n    elif rnode.connected:\n        node.bestval = max(lnode.bestval, lnode.rval + rnode.bestval+1)\n        node.lval = lnode.lval\n        node.rval = lnode.rval + rnode.bestval+1\n    else:\n        node.bestval = max(lnode.bestval, rnode.bestval, lnode.rval+rnode.lval+1)\n        node.lval = lnode.lval\n        node.rval = rnode.rval\n    node.connected = False\n\ndef query(l,r,idx, hnode):\n    if l > r or idx < l:\n        nnode = Node()\n        nnode.bestval = -1\n        nnode.lval = -1\n        nnode.rval = -1\n        return nnode\n    mid = (l+r)//2\n    if idx >= r:\n        return Node(False, hnode)\n    if l<=idx<=r:\n        mid = (l+r)//2\n        lnode = query(l, mid, idx, hnode.left)\n        rnode = query(mid+1, r, idx, hnode.right)\n        node = Node()\n        if lnode.connected and rnode.connected:\n            node.bestval = lnode.bestval + rnode.bestval+1\n            node.lval = node.bestval\n            node.rval = node.bestval\n        elif lnode.connected:\n            node.bestval = max(lnode.bestval + rnode.lval+1, rnode.bestval)\n            node.lval = lnode.bestval + rnode.lval+1\n            node.rval = rnode.rval\n        elif rnode.connected:\n            node.bestval = max(lnode.bestval, lnode.rval + rnode.bestval+1)\n            node.lval = lnode.lval\n            node.rval = lnode.rval + rnode.bestval+1\n        else:\n            node.bestval = max(lnode.bestval, rnode.bestval, lnode.rval+rnode.lval+1)\n            node.lval = lnode.lval\n            node.rval = rnode.rval\n        node.connected = False\n        return node\n\ndef ptrees(l,r,node):\n    if l > r:\n        return\n    if l == r:\n        return \n    mid = (l+r)//2\n    ptrees(l, mid, node.left)\n    ptrees(mid+1, r, node.right)\n\nclass Solution:\n    def getResults(self, queries: List[List[int]]) -> List[bool]:\n        ans = []\n        arr = max([i[1] for i in queries])+1\n        head = Build(0, arr-1, arr)\n        for curr in queries:\n            if curr[0] == 1:\n                x = curr[1]\n                temp = head\n                update(0, arr-1, x, temp)\n            else:\n                x,sz = curr[1], curr[2]\n                temp = head\n                nnode = query(0, arr-1, x, temp)\n                ans.append(nnode.bestval >= sz)\n            # print(head.bestval)\n            \n        return ans\n```
['Python3']