Java | Square root decomposition | without segment tree | O(sqrt(N) * N)
Intuition\nlet point 0 be 1 obstacle and infinity (1000000) be another. Each query of type 1 will place another obstacle.\nwe need to find a gap between two obs
# Intuition\nlet point 0 be 1 obstacle and infinity (1000000) be another. Each query of type 1 will place another obstacle.\nwe need to find a gap between two obstacle such that it can fit the block. Each node will store distance from next obstacle from its own point. We need to find max within a range\n\n# Approach\nSquare root decomposition method to store distance from next obstacle\n\n\n# Complexity\n- Time complexity: O(sqrt(N) * N)\n\n- Space complexity: O(N)\n\n# Code\n```java []\nclass Solution {\n    int[] sq;\n    int[] arr;\n    int xMax = 1000000;\n    int root;\n    TreeSet<Integer> seti;\n    public List<Boolean> getResults(int[][] queries) {\n        root = (int)Math.ceil(Math.sqrt(xMax));\n        sq = new int[root];\n        arr = new int[xMax];\n        seti = new TreeSet<>();\n        seti.add(0);\n        seti.add(1000000);\n        sq[0]=1000000;\n        arr[0]=1000000;\n        List<Boolean> re = new ArrayList<>();\n        for(int[] q : queries){\n            if(q[0]==1){\n                updateSq(q[1]);\n            }else{\n                int max = findmax(q[1]);\n                if(max>=q[2]){\n                    re.add(true);\n                }else{\n                    re.add(false);\n                }\n            }\n        }\n\n        return re;\n    }\n\n    int findmax(int ind){\n        int max=-1;\n        int l=0, r=seti.floor(ind-1);\n\n        //check distance between ind and prev obstacle. We cant take whole value of prev coz ind could be in between prev and its next \n        max = Math.max(ind-r, max);\n\n\n        //check distance for each blocks before prev objstacle\n        for(; l+root<r; ){\n            int blk = l/root;\n            max=Math.max(max, sq[blk]);\n            l+=root;\n        }\n\n        //remaining nodes\n        for(; l<r; l++){\n            max=Math.max(arr[l], max);\n        }\n\n        return max;\n    }\n\n    void updateSq(int ind){\n        int prev = seti.floor(ind);\n        int ceil = seti.ceiling(ind);\n        seti.add(ind);\n\n        arr[prev] = ind-prev;\n        arr[ind] = ceil-ind;\n\n        //update block of previous obstacle\n        int blknum = prev/root;\n        int blkStart = (prev/root)*root;\n        int blkEnd = blkStart+root-1;\n        int max=-1;\n        for(int i=blkStart; i<=blkEnd; i++ ){\n            max=Math.max(max, arr[i]);\n        }\n        sq[blknum] = max;\n\n        //update block of new obstacle\n        blknum = ind/root;\n        blkStart = (ind/root)*root;\n        blkEnd = blkStart+root-1;\n        max=-1;\n        for(int i=blkStart; i<=blkEnd; i++ ){\n            max=Math.max(max, arr[i]);\n        }\n        sq[blknum] = max;\n    }\n}\n```
['Java']