Evolve from intuition
O(n^2) Store the height of fallen squares as interval heights [left, right, height]. When a new square falls, we check intersection with existing intervals and 
1. O(n^2) Store the height of fallen squares as interval heights [left, right, height]. When a new square falls, we check intersection with existing intervals and compute the height of the new interval. Existing interval height does not need to be updated because we are only interested in the max height. Outdated lower interval height does not impact computing the max height. The idea is from [@leuction](https://leetcode.com/problems/falling-squares/discuss/108766/Easy-Understood-O(n2)-Solution-with-explanation).\n```\n\tpublic List<Integer> fallingSquares(int[][] positions) {\n        List<int[]> squares=new ArrayList<>();\n        List<Integer> res=new ArrayList<>();\n        for(int[] square:positions) {\n            int[] fs=new int[]{square[0],square[0]+square[1],square[1]};\n            int height=getHeight(fs,squares);\n            res.add(height);\n            squares.add(fs);\n        }          \n        return res;\n    }\n    private int getHeight(int[] cur, List<int[]> squares) {\n        int height=0, preMax=0;\n        for(int[] square:squares) {\n            preMax=Math.max(preMax,square[2]);\n            if(square[0]>=cur[1]||square[1]<=cur[0]) continue;\n            height=Math.max(height,square[2]);\n        }\n        return Math.max(preMax,cur[2]+=height);\n    }\n```\n2. O(nlogn) Intuitively, there should be a way to store the intervals in binary search tree so that get is O(logn). The idea is to represent the outline of the squares the same way as in 218. The Skyline Problem. In the worset case, each point is added, visited and removed. The idea is from [@britishorthair](https://leetcode.com/problems/falling-squares/discuss/112678/Treemap-solution-and-Segment-tree-(Java)-solution-with-lazy-propagation-and-coordinates-compression).\n![image](https://assets.leetcode.com/users/images/39a7151f-159f-4fe1-b012-12d31e33060a_1598741050.8380933.png)\n\n\n```\n\tpublic List<Integer> fallingSquares(int[][] positions) {\n        List<Integer> res=new ArrayList<>();\n        TreeMap<Integer,Integer> tm=new TreeMap<>();\n        tm.put(0,0);\n        int max=0;\n        for(int[] square:positions) {\n            int start=square[0], end=square[0]+square[1];\n            int left=tm.floorKey(start);\n            Map<Integer,Integer> map=tm.subMap(left, end);\n            int height=0;\n            for(int h:map.values()) \n                height=Math.max(h,height); \n            height+=square[1];\n            max=Math.max(max,height);   \n            res.add(max);\n            int curHeight=tm.floorEntry(end).getValue();\n            tm.put(start,height);\n            tm.put(end, curHeight);\n            tm.subMap(start,false,end,false).clear();\n        }          \n        return res;\n    }\n```\n
[]