Java 14ms, beats 99.38% using interval tree
java\nclass Solution {\n    \n    class Node {\n        public int l;\n        public int r;\n        public int max;\n        public int height;\n        publi
```java\nclass Solution {\n    \n    class Node {\n        public int l;\n        public int r;\n        public int max;\n        public int height;\n        public Node left;\n        public Node right;\n        \n        public Node (int l, int r, int max, int height) {\n            this.l = l;\n            this.r = r;\n            this.max = max;\n            this.height = height;\n        }\n    }\n    \n    \n    private boolean intersect(Node n, int l, int r) {\n        if (r <= n.l || l >= n.r) {\n            return false;\n        }\n        return true;\n    }\n    \n    private Node insert(Node root, int l, int r, int height) {\n        if (root == null) {\n            return new Node(l, r, r, height);\n        }\n        \n        if (l <= root.l) {\n            root.left = insert(root.left, l, r, height);\n        } else {\n             // l > root.l\n            root.right = insert(root.right, l, r, height);\n        }\n        root.max = Math.max(r, root.max);\n        return root;\n    }\n    \n    // return the max height for interval (l, r)\n    private int maxHeight(Node root, int l, int r) {\n        if (root == null || l >= root.max) {\n            return 0;\n        }\n        \n        int res = 0;\n        if (intersect(root, l, r)) {\n            res = root.height;\n        }\n        if (r > root.l) {\n            res = Math.max(res, maxHeight(root.right, l, r));\n        }\n        res = Math.max(res, maxHeight(root.left, l, r));\n        return res;\n    }\n    \n    public List<Integer> fallingSquares(int[][] positions) {\n        Node root = null;\n        List<Integer> res = new ArrayList<>();\n        int prev = 0;\n        \n        for (int i = 0; i < positions.length; ++i) {\n            int l = positions[i][0];\n            int r = positions[i][0] + positions[i][1];\n            int currentHeight = maxHeight(root, l, r);\n            root = insert(root, l, r, currentHeight + positions[i][1]);\n            prev = Math.max(prev, currentHeight + positions[i][1]);\n            res.add(prev);\n        }\n        \n        return res;\n    }\n}\n```
[]