Max gap - divide and conquer
Intuition\nTo get some inutition, suppose that we already got several obstacle position queries, say $[4, 7, 13, 18]$, and then reached a block query $(x,sz)$. 
# Intuition\nTo get some inutition, suppose that we already got several obstacle position queries, say $[4, 7, 13, 18]$, and then reached a block query $(x,sz)$. \nAs the block should be inserted before $x$, we should only care about the obstacles before it. So for example, if $x=12$, we should think of our obstacles as $[4,7,x=12]$.\nNext we want to go over each obstacle, and see if the gap right before it is enough to contain a block of size $sz$. In our case we have gaps $(0,4), (4,7), (7,12)$ of sizes $4,3,5$ respectively.\n\nThis approach already gives us a solution:\n1. Keep a sorted list of the obstacle positions. Total time complexity is $O(n\\cdot\\log(n))$).\n2. Given a block query, run over that list, and check if we can insert such a block. Each such call is $O(n)$ for a total of $O(n^2)$ time complexity.\n\nOf course, we would like to improve the running time of the second task, leading to the problem:\n**Question**: How can we find the maximal gap below the upper bound $x$?\n\nAs the example above shows, this can be decomposed into two parts:\n- The gap between $x$ and the largest obstacle smaller than $x$ (in the example above it is $(7,x=12)$). Note that this will not be well defined if $x$ is smaller than the smallest obstacle, however, we can (and should) always add an obstacle at $0$ to avoid this problem.\n- Finding the maximal gap up to the largest obstacle below $x$.\n\nThe decomposition is helpful since the first part is (realtively) easy to compute, while the second part only needs information about every obstacle, and not every $x$.\n**Question**: How can we find the maximal gap below each obstacle?\n\nGiven the obstacles, we can compute the max gap below each obstacle in $O(n)$ time, and then easily answer each following block type query. The problem is of course that extra obstacle position queries force us to update this "max gap" data, and we need to do it efficiently.\n\nFortunately, this **max** type problem enjoys the property that $\\max(A\\cup B) = max(max(A) , \\max(B))$. So if we already computed the **max** for the smaller sets, it is easy to compute the **max** for their large union. \n\nAs an example, suppose that we started with obstacle set\n$$[0,3,7,9,11,16,20,25,31].$$\nThe gaps are then $3,4,2,2,5,4,5,6$ and the max gap is 6. If we added an obstacle at point $28$, splitting the $[25,31]$ interval into $[25,28],[28,31]$, the 6 gap splits into two 3 gaps. Recomputing the max gap to get 5 will take $O(n)$ time. However, using the standard divide and conquer (of intervals), we can add some max gaps of subintervals as follows\n![image.png](https://assets.leetcode.com/users/images/457efb99-2012-4c3e-99cd-0ce6bdb79ca8_1723638826.5350811.png)\n\nNow, when we split the interval $[25,31]$ into two, we only need to update the max gaps "above it", and there are only $O(log(n))$ updates (or 4 in the image).\n\nIf we manage to do all of this together, we should expect an $O(n\\cdot log(n))$ time complexity, which is quite good.\n\n**Remark**: Probably the most important part in this solution is the "divide and conquer" property of the **max** function. Once such a function appears in a problem, you should probably look for a tree like struture which might help in the solution.\n\n\n# The Algorithm\nNow that we have the basic ideas, we need to actually implement them. As described above, there are two parts: (1) maintaining the data structure of the max gaps, and (2) Querying it.\n\n## The max gap data strucutre\nOur data structure will be a binary tree such that the leaves are the basic (consecutive) intervals, and each node should contain the max size (=max gap) of the intervals below it. For example, we can have two leaves corresponding to $[11,16]$ and $[16,20]$ and their parent corresponds to $[11,16]\\sqcup [16,20]$ with max gap = $5$.\n\nTo keep our solution running fast, we want the tree to be as short as possible, so you can choose any algorithm which does it. In my solution I used AVL trees, and to maintain it I added to each node \n1. the union interval edge points (e.g. $[11,20]$), and\n2. the height of the tree rooted at this node.\n\nWe can initialize the tree with the interval $[0,\\infty]$. Note that given the bounds in the question, we can find $MAX_N$ large enough that all the blocks will be in $[0,MAX_N]$, and use it as root instead.\n\n## Updating the max gaps\nWhen adding a new obstacle, exactly one leaf in the tree splits. The AVL insertion updates only $O(\\log(n))$ nodes, and keep the tree balanced. All the data in the node can be easily constructed from its two children: The intervar is the union of the children\'s intervals, the height is the max height of the children + 1, and most importantly the max gap is the max of the max gaps in the children. So an update command takes $O(\\log(n))$ time.\n\n## Querying the max gaps structure\nGiven a block query $(x,sz)$, we query our max gaps tree. Given a node, we want to ask whether a block of size $sz$, can fit inside one of the intervals below that node, and in $[0,x]$\n\nStarting from the root interval $[0,MAX_N]$, we have that $x$ is contained this interval. From now, we walk along nodes which satisfy this property as well.\n\n**QUERY($[a,b]$,x,sz):**\nSuppose we are in the (union) interval $[a,b]$:\n1. The node is a basic interval $[a,b]$: return $a+sz \\leq \\min(b,x)$.\n2. Otherwise, the node is a union of its children $[a,b]=[a,c]\\cup [c,b]$.\n    - If $x\\leq c$, the right part of the interval does not play a role, so return **QUERY($[a,c]$, x, sz)**.\n    - If $c < x$, then either the block can already fit in the left part of the interval, or we need to use the right part. In other words, return  \n      **$sz\\leq maxgap([a,b])$ or QUERY($[c,b]$, x, sz)**\n\nAs each time we go down to at most one child, this will take $O(\\log(n))$.\n\n# Complexity\n- Time complexity: $O(n\\log(n))$\n\n- Space complexity: $O(n)$\n\n# Code\n```\nINTERVAL = 0 = 0\nMAX_GAP = 1\nHEIGHT = 2\nLEFT_NODE = 3\nRIGHT_NODE = 4\n\n# AVL insert implementation\n\ndef combine(first_side, data_first, data_second):\n    """\n    combine two nodes to generate a parent node.\n    The first_side parameter tell whether the first data node is the left or right side\n    """\n\n    if first_side == LEFT_NODE:\n        data_left = data_first\n        data_right = data_second\n    else:\n        data_left = data_second\n        data_right = data_first\n\n    return [\n        (data_left[INTERVAL][0], data_right[INTERVAL][1]),\n        max(data_left[MAX_GAP], data_right[MAX_GAP]),\n        1 + max(data_left[HEIGHT], data_right[HEIGHT]),\n        data_left, data_right\n    ]\n\n\ndef insert(node, point):\n    """\n    Insert an obstacle at point to the union interval rooted at the node, under the assumption\n    that the point is in the interval.\n    Returns the new node, with the promise that its tree is balanced\n    """\n    \n    if node[HEIGHT] == 0:\n        # split a leaf node\n        left_edge, right_edge = node[INTERVAL]\n        node[LEFT_NODE] = [(left_edge, point), point - left_edge, 0, None, None]\n        node[RIGHT_NODE] = [(point, right_edge), right_edge - point, 0, None, None]\n        node[HEIGHT] = 1\n        node[MAX_GAP] = max(node[LEFT_NODE][MAX_GAP], node[RIGHT_NODE][MAX_GAP])\n        return node\n\n    if point <= node[LEFT_NODE][INTERVAL][1]:\n        a_side = LEFT_NODE\n        b_side = RIGHT_NODE\n    else:\n        a_side = RIGHT_NODE\n        b_side = LEFT_NODE\n\n    a_child = insert(node[a_side], point)\n    b_child = node[b_side]\n    \n    # AVL rotations:\n    if a_child[HEIGHT] > b_child[HEIGHT] + 1:\n        a_a_child = a_child[a_side]\n        a_b_child = a_child[b_side]\n        if a_a_child[HEIGHT] > a_b_child[HEIGHT]:\n            a_child = a_a_child\n            b_child = combine(a_side, a_b_child, b_child)\n        else:\n            a_b_a_child = a_b_child[a_side]\n            a_b_b_child = a_b_child[b_side]\n            a_child = combine(a_side, a_a_child, a_b_a_child)\n            b_child = combine(a_side, a_b_b_child, b_child)\n\n    return combine(a_side, a_child, b_child)\n\n\n\nclass Solution(object):\n\n    def getResults(self, queries):\n        """\n        :type queries: List[List[int]]\n        :rtype: List[bool]\n        """\n\n        max_obstacle = min(10**5, 6*len(queries))\n\n        root = [(0, max_obstacle), max_obstacle, 0, None, None]\n\n        results = []\n\n\n        for query in queries:\n            if query[0] == 1:\n                _, x = query\n                root = insert(root, x)\n            else:\n                _, x, size = query\n                node = root\n\n                while (True):\n                    if node[HEIGHT] == 0:\n                        # basic interval\n                        results.append(node[INTERVAL][0] + size <= x)\n                        break\n\n                    left_node = node[LEFT_NODE]\n                    if x <= left_node[INTERVAL][1]:\n                        node = node[LEFT_NODE]\n                        continue\n\n                    if size <= left_node[MAX_GAP]:\n                        results.append(True)\n                        break\n\n                    node = node[RIGHT_NODE]\n\n        return results\n```
['Python']