Clean And Concise Lazy Propagation Segment Tree
\nclass Solution {\n    public List<Integer> fallingSquares(int[][] positions) {\n        SegmentNode root = new SegmentNode(0,Integer.MAX_VALUE,0);\n        Li
```\nclass Solution {\n    public List<Integer> fallingSquares(int[][] positions) {\n        SegmentNode root = new SegmentNode(0,Integer.MAX_VALUE,0);\n        List<Integer> ans = new ArrayList<>();\n        int max = 0;\n        for(int[] p : positions){\n            int left = p[0], height = p[1], right = left + height;\n            int maxHeight = query(root, left, right) + height;\n            max = Math.max(max,maxHeight);\n            ans.add(max);\n            add(root, left, right, maxHeight);\n        }\n        return ans;\n    }\n    public int query(SegmentNode root, int start, int end){\n        if(start<=root.start && end>=root.end) return root.maxHeight;\n        if(start>=root.end || end<=root.start) return  0;\n        if (root.left==null) return root.maxHeight;\n        int mid = root.start + (root.end - root.start) / 2;\n        if (end <= mid) {\n            return query(root.left, start, end);\n        } else if (start >= mid) {\n            return query(root.right, start, end);\n        }\n        return Math.max(query(root.left,start,mid),query(root.right,mid,end));\n    }\n\n    public void add(SegmentNode root, int start, int end, int maxHeight){\n        if(start<=root.start && end>=root.end){\n            root.maxHeight = maxHeight;\n            root.left = null;\n            root.right = null;\n            return;\n        }\n        if(start>=root.end || root.start>=end) return;\n        if(root.left==null){\n            int mid = root.start + (root.end - root.start) / 2;\n            root.left = new SegmentNode(root.start,mid,0);\n            root.right = new SegmentNode(mid,root.end,0);\n        }\n        add(root.left,start,end,maxHeight);\n        add(root.right,start,end,maxHeight);\n        root.maxHeight = Math.max(root.left.maxHeight,root.right.maxHeight);\n    }\n}\nclass SegmentNode{\n    public SegmentNode left , right;\n    public int start, end, maxHeight;\n    public SegmentNode(int start, int end, int maxHeight){\n        this.start = start;\n        this.end = end;\n        this.maxHeight = maxHeight;\n    }\n}\n```
['Tree', 'Java']