Segment Tree with HashMap
Intuition\nBrucefore should be O(nm)\n\n# Approach\nWe want to find the max gap between 0 to x with in log(n). I think out about using Segment tree for that pur
# Intuition\nBrucefore should be O(n*m)\n\n# Approach\nWe want to find the max gap between 0 to x with in log(n). I think out about using Segment tree for that purpose.\n\n# Complexity\n- Time complexity: O(n*log(m))\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# Code\n```go\nfunc getResults(queries [][]int) []bool {\n\tobs := make([]int, 0, 1<<5)\n\tres := make([]bool, 0, len(queries))\n\tst := NewSegmentTreeWithMap[int](5*1e4)\n\tfor _, q := range queries {\n\t\tidx, _ := slices.BinarySearch(obs, q[1])\n\t\tswitch q[0] {\n\t\tcase 1: // place obs\n\t\t\tobs = slices.Insert(obs, idx, q[1])\n\t\t\tprevObs := 0\n\t\t\tif idx > 0 {\n\t\t\t\tprevObs = obs[idx-1]\n\t\t\t}\n\t\t\tst.Update(obs[idx], obs[idx]-prevObs)\n\t\t\tif idx < len(obs)-1 {\n\t\t\t\tst.Update(obs[idx+1], obs[idx+1]-obs[idx])\n\t\t\t}\n\t\tcase 2:\n\t\t\tmaxGap := q[1]\n\t\t\tif idx > 0 {\n\t\t\t\tmaxGap = max(q[1]-obs[idx-1], st.Query(0, obs[idx-1]))\n\t\t\t}\n\t\t\tres = append(res, maxGap >= q[2])\n\t\t}\n\t}\n\treturn res\n}\n\ntype segmentTreeWithMap[T ~int] struct {\n\tdata             map[int]T\n\tsize             int\n}\n\ntype SegmentTree[T ~int] interface {\n\tQuery(lo, hi int) T\n\tUpdate(pos int, val T)\n}\n\nfunc NewSegmentTreeWithMap[T ~int](size int) SegmentTree[T] {\n\treturn &segmentTreeWithMap[T]{\n\t\tdata:             make(map[int]T),\n\t\tsize:             size,\n\t}\n}\n\nfunc (st *segmentTreeWithMap[T]) Query(lo, hi int) T {\n\tlo += st.size\n\thi += st.size\n\tres := st.data[hi]\n\tfor lo < hi {\n\t\tif lo&1 != 0 {\n\t\t\tres = max(res, st.data[lo])\n\t\t\tlo++\n\t\t}\n\t\tif hi&1 != 0 {\n\t\t\thi--\n\t\t\tres = max(res, st.data[hi])\n\t\t}\n\t\tlo >>= 1\n\t\thi >>= 1\n\t}\n\treturn res\n}\n\nfunc (st *segmentTreeWithMap[T]) Update(pos int, val T) {\n\tpos += st.size\n\tst.data[pos] = val\n\tfor pos > 1 {\n\t\tpos >>= 1\n\t\tst.data[pos] = max(st.data[2*pos], st.data[2*pos+1])\n\t}\n}\n```
['Go']