[Python3] Segment Tree (arrays only, without classes)
Complexity\n- Time complexity: O(N + M * log(N, 2))\n Add your time complexity here, e.g. O(n) \n\n- Space complexity: O(N)\n Add your space complexity here, e.
# Complexity\n- Time complexity: $$O(N + M * log(N, 2))$$\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`M` - length of queries\n\n`N` - max queried `x`\n\n# Code\n```\nclass Solution:\n    def getResults(self, queries: List[List[int]]) -> List[bool]:\n        deg2 = math.floor(math.log(max(x[1] for x in queries), 2)) + 1\n        n = 2 ** deg2\n        stsize = n * 2\n        l = [0] * stsize  # longest placement starting from the beginning of segment\n        r = [0] * stsize  # longest placement starting from the ending of segment\n        m = [0] * stsize  # longest placement overall in the segment\n\n        # inital filling of the segment tree\n        def fill(i=0, beg=0, size=n):\n            l[i] = r[i] = m[i] = size\n            if size > 1:\n                li, ri = 2 * i + 1, 2 * i + 2\n                hsize = size // 2\n                fill(li, beg, hsize)\n                fill(ri, beg + hsize, hsize)\n        \n        fill()\n\n        # insert barrier operation\n        def insert(x, i=0, beg=0, size=n):\n            if size == 1:\n                if x > beg:\n                    r[i] = 0\n                else:\n                    l[i] = 0\n            else:\n                li, ri = 2 * i + 1, 2 * i + 2\n                hsize = size // 2\n                mid = beg + hsize\n                if x <= mid:\n                    insert(x, li, beg, hsize)\n                if x >= mid:\n                    insert(x, ri, mid, hsize)\n                l[i] = l[li] + (l[ri] if l[li] == hsize else 0)\n                r[i] = r[ri] + (r[li] if r[ri] == hsize else 0)\n                m[i] = max(l[i], r[i], m[li], m[ri], r[li] + l[ri])\n\n        # query\n        # returns (left, max) \n        # where `left` is max block size starting at the beginning of the segement (considering x constraint)\n        # `max` is max block size overall in the chosen segment (considering x constraint)\n        def get_max(x, i=0, beg=0, size=n):\n            if size == 1:\n                if x > beg:\n                    return l[i], m[i]\n                else:\n                    return 0, 0\n            li, ri = 2 * i + 1, 2 * i + 2\n            hsize = size // 2\n            mid = beg + hsize\n            if x <= mid:\n                return get_max(x, li, beg, hsize)\n            lri, mr = get_max(x, ri, beg + hsize, hsize)\n            lpart = l[li] + (lri if l[li] == hsize else 0)\n            return lpart, max(m[li], mr, lpart, r[li] + lri)\n\n        ret = []\n        for q in queries:\n            if q[0] == 1:\n                insert(q[1])\n            else:\n                ret.append(get_max(q[1])[1] >= q[2])\n        return ret\n\n\n```
['Python3']