Efficiently Solving the Infinite Number Line Problem with Obstacles Using Segment Trees
Introduction\nThe problem at hand involves managing an infinite number line with obstacles and determining if we can place a block of a certain size within a sp
**Introduction**\nThe problem at hand involves managing an infinite number line with obstacles and determining if we can place a block of a certain size within a specified range. Given the constraints and operations, the challenge is to handle these queries efficiently. This article explores an optimized solution using segment trees, ensuring both time and space efficiency.\n**Problem Statement**\nYou are given a 2D array queries, containing two types of queries:\n\n[1, x]: Place an obstacle at distance x from the origin.\n[2, x, sz]: Check if it is possible to place a block of size sz entirely within the range [0, x] on the number line without intersecting any obstacles.\nThe goal is to return a boolean array results where each element corresponds to the result of the respective type 2 query.\n\n**Constraints**\n1 <= queries.length <= 15 * 10^4\n1 <= x, sz <= min(5 * 10^4, 3 * queries.length)\nThe number line and the queries are such that no two consecutive queries place an obstacle at the same position.\nApproach\nTo solve this problem efficiently, we use a combination of sorted lists and segment trees. Here\u2019s the detailed breakdown of our approach:\n\n**Data Structures**\nObstacles List: A sorted list to keep track of the positions of the obstacles. This helps in efficiently finding the nearest obstacles around a given position.\nSegment Tree: A segment tree to manage and query the maximum gaps between consecutive obstacles. This allows us to quickly determine if there\u2019s a sufficient gap to place the block.\n**Operations**\nInserting Obstacles\nWhen inserting an obstacle:\n\nFind the position to insert the obstacle in the sorted list.\nUpdate the segment tree to reflect the new gaps created by this obstacle.\nQuerying for Block Placement\nFor each type 2 query:\n\nUse the segment tree to find the maximum gap within the specified range.\nDetermine if the block can be placed based on this gap.\n\n# Code\n```\n\ntype SegmentTree struct {\n\tdata map[int]int\n\tsize int\n}\n\nfunc NewSegmentTree(size int) *SegmentTree {\n\treturn &SegmentTree{\n\t\tdata: make(map[int]int),\n\t\tsize: size,\n\t}\n}\n\nfunc (st *SegmentTree) Query(lo, hi int) int {\n\tlo += st.size\n\thi += st.size\n\tres := 0\n\tfor lo <= hi {\n\t\tif lo&1 == 1 {\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\tres = max(res, st.data[hi])\n\t\t\thi--\n\t\t}\n\t\tlo >>= 1\n\t\thi >>= 1\n\t}\n\treturn res\n}\n\nfunc (st *SegmentTree) Update(pos, val int) {\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\nfunc getResults(queries [][]int) []bool {\n\tobstacles := []int{}\n\tresults := []bool{}\n\tst := NewSegmentTree(5 * 1e4)\n\tfor _, q := range queries {\n\t\tif q[0] == 1 {\n\t\t\t// Insert an obstacle at q[1]\n\t\t\tx := q[1]\n\t\t\tidx := sort.SearchInts(obstacles, x)\n\t\t\tobstacles = append(obstacles, 0)\n\t\t\tcopy(obstacles[idx+1:], obstacles[idx:])\n\t\t\tobstacles[idx] = x\n\n\t\t\tleft := 0\n\t\t\tif idx > 0 {\n\t\t\t\tleft = obstacles[idx-1]\n\t\t\t}\n\t\t\tst.Update(x, x-left)\n\t\t\tif idx < len(obstacles)-1 {\n\t\t\t\tst.Update(obstacles[idx+1], obstacles[idx+1]-x)\n\t\t\t}\n\t\t} else if q[0] == 2 {\n\t\t\t// Check if a block of size q[2] can be placed within [0, q[1]]\n\t\t\tx, sz := q[1], q[2]\n\t\t\tidx := sort.SearchInts(obstacles, x)\n\t\t\tmaxGap := x\n\t\t\tif idx > 0 {\n\t\t\t\tmaxGap = max(x-obstacles[idx-1], st.Query(0, obstacles[idx-1]))\n\t\t\t}\n\t\t\tresults = append(results, maxGap >= sz)\n\t\t}\n\t}\n\treturn results\n}\n\nfunc max(a, b int) int {\n\tif a > b {\n\t\treturn a\n\t}\n\treturn b\n}\n\n```
['Go']