Java segment tree O(position.length * log(max_range))
My first segment tree ever.\n\n\n    class SegNode {\n        int left, mid, right;\n        int max;\n        boolean modified;\n        SegNode leftChild, rig
My first segment tree ever.\n```\n\n    class SegNode {\n        int left, mid, right;\n        int max;\n        boolean modified;\n        SegNode leftChild, rightChild;\n        SegNode(int left, int right, int max){\n            this.left=left;\n            this.right=right;\n            this.mid=left+(right-left)/2;\n            this.max=max;\n        }\n        int query(int left, int right){\n            int ans;\n            if ((left<=this.left&&right>=this.right)||this.leftChild==null){\n                ans=this.max;\n            }\n            else {\n                pushdown();\n                ans = Integer.MIN_VALUE;\n                if (left <= this.mid && this.leftChild != null)\n                    ans = Math.max(ans, leftChild.query(left, Math.min(this.mid, right)));\n                if (right > this.mid && this.rightChild != null)\n                    ans = Math.max(ans, rightChild.query(Math.max(this.mid + 1, left), right));\n            }\n//            log.info("query on ({},{}) is {}, this.left, right, max: ({}, {}, {})", left, right, ans, this.left,this.right,this.max);\n            return ans;\n        }\n        void pushdown(){\n            if (this.leftChild!=null){\n                if (this.modified) {\n                    this.leftChild.modified=true;\n                    this.leftChild.max=max;\n                    this.rightChild.modified=true;\n                    this.rightChild.max=max;\n                }\n            } else {\n                this.leftChild=new SegNode(left, mid, max);\n                this.rightChild=new SegNode(mid+1,right, max);\n\n            }\n        }\n\n        void insert(int left, int right, int value){\n\n//            log.info("insert {}, {}, {} on ({}, {})", left, right, value, this.left, this.right);\n            if (left<=this.left && right>=this.right){\n                if (value>this.max) {\n                    this.max = Math.max(this.max, value);\n                    modified=true;\n                }\n\n            } else {\n                pushdown();\n                if (left<=mid) this.leftChild.insert(left, Math.min(mid, right), value);\n                if (right>mid)this.rightChild.insert(Math.max(mid+1, left), right, value);\n                this.max=Math.max(this.leftChild.max, this.rightChild.max);\n                modified=false;\n            }\n        }\n    }\n\n    public List<Integer> fallingSquares(int[][] positions) {\n        List<Integer> ans=new ArrayList<>();\n        int left=0, right=1_000_000_000;\n        if (positions.length==0)return ans;\n        SegNode root=new SegNode(left, right, 0);\n        int oldPeek=0;\n        for (int[] rec: positions){\n            int curMax=root.query(rec[0], rec[0]+rec[1]-1);\n//            log.info("curMax on ({},{}): {}", rec[0], rec[0]+rec[1]-1, curMax);\n\n            int newMax=curMax+rec[1];\n            oldPeek=Math.max(oldPeek, newMax);\n            ans.add(oldPeek);\n            root.insert(rec[0], rec[0]+rec[1]-1, newMax);\n        }\n        return ans;\n\n    }\n```
[]