C++ Segment Tree with explaination and comments
We can use a segment tree to find the maximum element within a range in log(n) time (see here for an explaination).\n\nFor a query of type 2, we can therefore c
We can use a segment tree to find the maximum element within a range in $$log(n)$$ time (see [here](https://cp-algorithms.com/data_structures/segment_tree.html) for an explaination).\n\nFor a query of type 2, we can therefore check a segment tree tracking the max gap between obstacles within the range $$[0, x]$$.\n\nHowever, it gets tricky with queries of type 1. In this case we need to replace a single entry in this segment tree with 2 new ones, because some gap $$[l,r]$$, where $$l < x < r$$, will become two gaps, $$[l,x]$$ and $$[x,r]$$. Segment trees do not allow for inserts or removals, so we can\'t do this directly.\n\nHowever,\n- Segment trees do allow for updating an existing element\'s value.\n- Since we are querying for the max, a value of `0` is essentially an "empty" entry so we can initialize the segment tree with all zeros.\n- We know there is a limit of $$5*10^4$$ for obstacle placement and obstacles are placed discretely and uniquely.\n\nGiven this, we can insert gap values such that they represent the gap from that obstacle index going back to the previous one, and all the `0`\'s in-between obstacles will just be ignored. \n\nThe "*remove and insert two new elements*" becomes "*update two existing elements*". In particular, one already non-zero element gets decreased at index $$r$$, and another 0 element gets "set" at index $$x$$.\n\nIn order to find index $$r$$, we can keep track of all existing obstacles in an ordered set and find it in $$log(n)$$ time with `lower_bound(x)`.\n\n# Complexity\n- Time complexity: $$O(n*log(n))$$ -->\n\n- Space complexity: $$O(n)$$\n\n# Code\n```\nconstexpr int MaxX = 50001;\n\nclass SegTree;\n\nclass Solution\n{\npublic:\n\tvector<bool> getResults(vector<vector<int>>& queries)\n\t{\n\t\tSegTree seg(MaxX);\n\t\tset<int> obs;\n        // Consider the max x and 0 as existing obstacles\n\t\tobs.insert(0);\n\t\tobs.insert(MaxX);\n\n\t\tvector<bool> ans;\n\t\tfor (auto& q : queries)\n\t\t{\n\t\t\tint x = q[1];\n\t\t\tif (q[0] == 1)\n\t\t\t{\n                // x will never already exist in obs, so the returned itr will\n                // always be r of the existing gap and l will be the prevous one\n\t\t\t\tauto itr = obs.upper_bound(x);\n\t\t\t\tint r = *itr;\n\t\t\t\tint l = *(--itr);\n\t\t\t\tobs.insert(x);\n\t\t\t\tseg.UpdateValue(x, x - l);\n\t\t\t\tseg.UpdateValue(r, r - x);\n\t\t\t}\n\t\t\telse\n\t\t\t{\n\t\t\t\tint sz = q[2];\n                // First check the segment tree for the max gap before x\n\t\t\t\tbool isValid = seg.GetMax(x) >= sz;\n                // But if we don\'t find one,\n                // then we should also check the gap which x falls into\n                // as there is the space from [l,x] which is not accounted for\n                // in the segment tree if no obstable exists at x\n\t\t\t\tif (!isValid)\n\t\t\t\t{\n\t\t\t\t\tauto itr = obs.lower_bound(x);\n\t\t\t\t\tif (*itr != x)\n\t\t\t\t\t{\n                        int l = *(--itr);\n\t\t\t\t\t\tisValid = (x - l) >= sz;\n\t\t\t\t\t}\n\t\t\t\t}\n\t\t\t\tans.push_back(isValid);\n\t\t\t}\n\t\t}\n\n\t\treturn ans;\n\t}\n};\n\nclass SegTree\n{\npublic:\n\tSegTree(int _n)\n\t{\n\t\tn = _n;\n\t\ttree.resize(n * 4, 0);\n\t}\n\n\tint GetMax(int x) const\n\t{\n\t\treturn GetRangeValueInternal(0, x, 1, 0, n - 1);\n\t}\n\n\tvoid UpdateValue(int index, int newValue)\n\t{\n\t\tUpdateValueInternal(index, newValue, 1, 0, n - 1);\n\t}\n\nprivate:\n\tint GetRangeValueInternal(int left, int right, int nodeIndex, int nodeRangeLeftIndex, int nodeRangeRightIndex) const\n\t{\n\t\tif (left > right)\n\t\t\treturn 0;\n\n\t\tif (left == nodeRangeLeftIndex && right == nodeRangeRightIndex)\n\t\t\treturn tree[nodeIndex];\n\n\t\tint rangeMid = (nodeRangeLeftIndex + nodeRangeRightIndex) / 2;\n\t\tint leftV = GetRangeValueInternal(left, min(right, rangeMid), nodeIndex * 2, nodeRangeLeftIndex, rangeMid);\n\t\tint rightV = GetRangeValueInternal(max(left, rangeMid + 1), right, nodeIndex * 2 + 1, rangeMid + 1, nodeRangeRightIndex);\n\t\treturn max(leftV, rightV);\n\t}\n\n\tvoid UpdateValueInternal(int index, int newValue, int nodeIndex, int nodeRangeLeftIndex, int nodeRangeRightIndex)\n\t{\n\t\tif (nodeRangeLeftIndex == nodeRangeRightIndex)\n\t\t{\n\t\t\ttree[nodeIndex] = newValue;\n\t\t\treturn;\n\t\t}\n\n\t\tint mid = (nodeRangeLeftIndex + nodeRangeRightIndex) / 2;\n\t\tint leftChild = nodeIndex * 2;\n\t\tint rightChild = leftChild + 1;\n\t\tif (index <= mid)\n\t\t{\n\t\t\tUpdateValueInternal(index, newValue, leftChild, nodeRangeLeftIndex, mid);\n\t\t}\n\t\telse\n\t\t{\n\t\t\tUpdateValueInternal(index, newValue, rightChild, mid + 1, nodeRangeRightIndex);\n\t\t}\n\t\ttree[nodeIndex] = max(tree[leftChild], tree[rightChild]);\n\t}\n\n\tint n;\n\tvector<int> tree;\n};\n```
['Segment Tree', 'C++']