Java Solution - Segment Tree
\nclass Solution {\n    \n    private Node root;\n    \n    public List<Integer> fallingSquares(int[][] positions) {\n        // \u7EBF\u6BB5\u6811\n        int
```\nclass Solution {\n    \n    private Node root;\n    \n    public List<Integer> fallingSquares(int[][] positions) {\n        // \u7EBF\u6BB5\u6811\n        int max = (int) (1e9);\n        root = new Node(0, max);\n        List<Integer> res = new ArrayList<>();\n        for (int[] position : positions) {\n            int rangeMaxValue = query(root, position[0], position[0] + position[1] - 1);\n            update(root, position[0], position[0] + position[1] - 1, rangeMaxValue + position[1]);\n            int curGlobalMaxValue = query(root, 0, max);\n            res.add(curGlobalMaxValue);\n        }\n        return res;\n    }\n    \n    /**\n     * \u7EBF\u6BB5\u6811\u7684\u7ED3\u70B9\n     */\n    class Node {\n        private int leftX; // \u5DE6\u8303\u56F4\n        private int rightX; // \u53F3\u8303\u56F4\n        private int maxValue; // \u8303\u56F4\u5185\u7684\u6700\u5927\u503C\n        private int lazy; // \u61D2\u6807\u8BB0\n        Node leftChild, rightChild; // \u5DE6\u5B50\u6811\u548C\u53F3\u5B50\u6811\n\n        public Node(int leftX, int rightX) {\n            this.leftX = leftX;\n            this.rightX = rightX;\n        }\n    }\n\n    /**\n     * \u533A\u95F4\u6C42\u503C\n     *\n     * @param root  \u6811\u7684\u6839\n     * @param left  \u5DE6\u8FB9\u754C\n     * @param right \u53F3\u8FB9\u754C\n     */\n    public int query(Node root, int left, int right) {\n        // \u4E0D\u5728\u8303\u56F4\u5185 \u76F4\u63A5\u8FD4\u56DE\n        if (root.rightX < left || right < root.leftX) {\n            return 0;\n        }\n        // \u67E5\u8BE2\u7684\u533A\u95F4\u5305\u542B\u5F53\u524D\u7ED3\u70B9\n        if (left <= root.leftX && root.rightX <= right) {\n            return root.maxValue;\n        } else {\n            lazyCreate(root); // \u52A8\u6001\u5F00\u70B9\n            pushDown(root); // \u4E0B\u4F20 lazy\n            int l = query(root.leftChild, left, right); // \u6C42\u5DE6\u5B50\u6811\n            int r = query(root.rightChild, left, right); // \u6C42\u53F3\u5B50\u6811\n            return Math.max(l, r);\n        }\n    }\n\n    /**\n     * \u533A\u95F4\u66F4\u65B0\n     *\n     * @param root  \u6811\u7684\u6839\n     * @param left  \u5DE6\u8FB9\u754C\n     * @param right \u53F3\u8FB9\u754C\n     * @param value \u66F4\u65B0\u503C\n     */\n    public void update(Node root, int left, int right, int value) {\n        // \u4E0D\u5728\u8303\u56F4\u5185 \u76F4\u63A5\u8FD4\u56DE\n        if (root.rightX < left || right < root.leftX) {\n            return;\n        }\n        // \u4FEE\u6539\u7684\u533A\u95F4\u5305\u542B\u5F53\u524D\u7ED3\u70B9\n        if (left <= root.leftX && root.rightX <= right) {\n            root.maxValue = value;\n            root.lazy = value;\n        } else {\n            lazyCreate(root); // \u52A8\u6001\u5F00\u70B9\n            pushDown(root); // \u4E0B\u4F20 lazy\n            update(root.leftChild, left, right, value); // \u66F4\u65B0\u5DE6\u5B50\u6811\n            update(root.rightChild, left, right, value); // \u66F4\u65B0\u53F3\u5B50\u6811\n            pushUp(root); // \u4E0A\u4F20\u7ED3\u679C\n        }\n    }\n\n    /**\n     * \u521B\u5EFA\u5DE6\u53F3\u5B50\u6811\n     *\n     * @param root\n     */\n    public void lazyCreate(Node root) {\n        if (root.leftChild == null) {\n            root.leftChild = new Node(root.leftX, root.leftX + (root.rightX - root.leftX) / 2);\n        }\n        if (root.rightChild == null) {\n            root.rightChild = new Node(root.leftX + (root.rightX - root.leftX) / 2 + 1, root.rightX);\n        }\n    }\n\n    /**\n     * \u4E0B\u4F20 lazy\n     *\n     * @param root\n     */\n    public void pushDown(Node root) {\n        if (root.lazy > 0) {\n            root.leftChild.maxValue = root.lazy;\n            root.leftChild.lazy = root.lazy;\n            root.rightChild.maxValue = root.lazy;\n            root.rightChild.lazy = root.lazy;\n            root.lazy = 0;\n        }\n    }\n\n    /**\n     * \u4E0A\u4F20\u7ED3\u679C\n     *\n     * @param root\n     */\n    public void pushUp(Node root) {\n        root.maxValue = Math.max(root.leftChild.maxValue, root.rightChild.maxValue);\n    }\n}\n```
[]