EfficientBlockPlacementandObstacleManagementonanInfiniteLineUsingSegmentTrees-Java-104msbeats99%
Intuition\nThe problem revolves around managing obstacles on an infinite number line and checking the feasibility of placing blocks within a specific range. My 
# Intuition\nThe problem revolves around managing obstacles on an infinite number line and checking the feasibility of placing blocks within a specific range. My first thought was to efficiently manage the obstacles and quickly determine the largest free space available at any given position on the line. This led me to consider segment trees, which are well-suited for range queries and updates, making them ideal for this problem.\n\n# Approach\nThe approach uses a segment tree to manage the maximum free space between obstacles efficiently. The segment tree nodes store the range they cover, the maximum free space within that range, and the nearest obstacle within that range.\n\n1. Segment Tree Construction:\n    - Initialize a segment tree covering the entire possible range where obstacles can be placed.\n    - Each node in the segment tree represents a segment of the number line and stores the maximum free space in that segment and the nearest obstacle.\n\n2. Handling Obstacle Addition:\n    - When an obstacle is added at position x, update the segment tree to reflect this new obstacle.\n    - The segment tree nodes are updated to ensure they correctly represent the new maximum free space after the obstacle is added.\n\n3. Block Placement Query:\n    - For each query, check if a block of a given size can be placed within a specific range [0, x].\n    - Use the segment tree to efficiently determine the largest free space available before any obstacle in that range.\n\n# Complexity\n- Time complexity:\nBuilding the Segment Tree: Constructing the segment tree initially takes O(n) time, where n is the maximum range of the number line.\n\n- Space complexity:\nThe space complexity for the segment tree is O(n), where\nn is the maximum range of the number line that we need to cover. This includes the space needed for the segment tree nodes and the auxiliary data.\n\n# Code\n```java []\nimport java.util.*;\n\nclass Solution {\n    class SegmentTreeNode {\n        SegmentTreeNode leftChild;\n        SegmentTreeNode rightChild;\n        int start;\n        int end;\n        int maxFreeSpace = 0;\n        int nearestObstacle = Integer.MAX_VALUE;\n\n        SegmentTreeNode(int start, int end, int obstaclePosition) {\n            this.start = start;\n            this.end = end;\n            this.nearestObstacle = obstaclePosition;\n            this.maxFreeSpace = obstaclePosition == Integer.MAX_VALUE ? Integer.MAX_VALUE : obstaclePosition - start;\n        }\n\n        void printTree() {\n            System.out.print("[" + start + "-" + end + ": " + nearestObstacle + ", " + maxFreeSpace);\n            if (leftChild != null) {\n                System.out.print(" -- ");\n                leftChild.printTree();\n                rightChild.printTree();\n                System.out.print(" -- " + start + "-" + end);\n            }\n            System.out.print("]");\n        }\n    }\n    \n    public List<Boolean> getResults(int[][] queries) {\n        int maxRange = 0;\n        for (int[] query : queries) {\n            if (query[0] == 1) {\n                maxRange = Math.max(maxRange, query[1]);\n            }\n        }\n        SegmentTreeNode root = new SegmentTreeNode(0, maxRange, Integer.MAX_VALUE);\n        List<Boolean> results = new ArrayList<>();\n        for (int[] query : queries) {\n            if (query[0] == 1) {\n                addObstacle(root, query[1]);\n            } else {\n                int blockStart = query[1] - query[2];\n                if (blockStart >= root.end) {\n                    results.add(true);\n                } else {\n                    results.add(isBlockPlaceable(root, blockStart, query[2]));\n                }\n            }\n        }\n        return results;\n    }\n\n    boolean isBlockPlaceable(SegmentTreeNode root, int blockStart, int blockSize) {\n        if (root.leftChild == null && root.rightChild == null) {\n            if (blockStart >= root.end) {\n                return blockSize <= root.maxFreeSpace;\n            } else if (blockStart < root.start) {\n                return false;\n            } else {\n                return blockSize <= (root.nearestObstacle - root.start);\n            }\n        }\n\n        if (root.rightChild.end <= blockStart) {\n            if (root.rightChild.maxFreeSpace >= blockSize) {\n                return true;\n            }\n        }\n        if (root.leftChild.end <= blockStart) {\n            if (root.leftChild.maxFreeSpace >= blockSize) {\n                return true;\n            }\n        } else {\n            return isBlockPlaceable(root.leftChild, blockStart, blockSize);\n        }\n        if (root.rightChild.start <= blockStart && root.rightChild.end >= blockStart) {\n            return isBlockPlaceable(root.rightChild, blockStart, blockSize);\n        }\n\n        return false;\n    }\n\n    int addObstacle(SegmentTreeNode root, int obstaclePosition) {\n        if (root.end == root.start) {\n            root.nearestObstacle = (root.end < obstaclePosition && obstaclePosition < root.nearestObstacle) ? obstaclePosition : root.nearestObstacle;\n            root.maxFreeSpace = root.nearestObstacle == Integer.MAX_VALUE ? root.nearestObstacle : root.nearestObstacle - root.start;\n            return root.maxFreeSpace;\n        }\n        if (obstaclePosition <= root.start) return root.maxFreeSpace;\n        if (obstaclePosition > root.end) {\n            if (obstaclePosition < root.nearestObstacle) {\n                root.nearestObstacle = obstaclePosition;\n                if (root.leftChild == null && root.rightChild == null) {\n                    root.maxFreeSpace = (obstaclePosition - root.start);\n                } else {\n                    root.maxFreeSpace = Math.max(addObstacle(root.leftChild, obstaclePosition), addObstacle(root.rightChild, obstaclePosition));\n                }\n            }\n            return root.maxFreeSpace;\n        }\n        if (root.leftChild != null && root.rightChild != null) {\n            root.maxFreeSpace = Math.max(addObstacle(root.leftChild, obstaclePosition), addObstacle(root.rightChild, obstaclePosition));\n            return root.maxFreeSpace;\n        }\n        int mid = (root.end - root.start) / 2 + root.start;\n        root.leftChild = new SegmentTreeNode(root.start, mid, root.nearestObstacle);\n        root.rightChild = new SegmentTreeNode(mid + 1, root.end, root.nearestObstacle);\n        root.maxFreeSpace = Math.max(addObstacle(root.leftChild, obstaclePosition), addObstacle(root.rightChild, obstaclePosition));\n        return root.maxFreeSpace;\n    }\n\n    public static void main(String[] args) {\n        Solution solution = new Solution();\n        int[][] queries = {{1, 5}, {2, 7, 2}, {2, 6, 2}};\n        System.out.println(solution.getResults(queries));  // Output: [false, true]\n    }\n}\n\n```
['Array', 'Binary Search', 'Binary Indexed Tree', 'Segment Tree', 'Java']