3 Clean Incrementally Difficult Recursive Segment Tree (Simple, Compressed, Lazy)
I try to code recursive segment trees instead of array-based ones since they are easier to understand. Even if they are a bit slower, they still easily meet the
I try to code recursive segment trees instead of array-based ones since they are easier to understand. Even if they are a bit slower, they still easily meet the time limit for LeetCode and programming interviews.\n\nHere, I have 3 steadily harder implementations of the Segment Tree so that it is easier to understand.\n\n**Simple Segment Tree (Memory Exceeded)**\nUnfortunately, the range of values here is 1e9 which means that this will take too much memory and time. But this is the best for initial debugging with small test-cases.\n\n```\nclass Solution {\n    public List<Integer> fallingSquares(int[][] positions) {\n        SegmentTree sg = new SegmentTree((int)1e4);\n        int maxHeight = 0;\n        List<Integer> output = new ArrayList<>();\n        \n        for (int[] position: positions) {\n            int start = position[0];\n            int end = position[0] + position[1] - 1;\n            int heightInRange = sg.query(start, end);\n            int updatedHeightInRange = heightInRange + position[1];\n            maxHeight = Math.max(maxHeight, updatedHeightInRange);\n            output.add(maxHeight);\n            sg.update(start, end, updatedHeightInRange);\n        }\n        \n        return output;\n        \n    }\n    \n    class SegmentTree {\n        SegmentTreeNode root;\n        \n        public SegmentTree(int endIndex) {\n            root = new SegmentTreeNode(0, endIndex);\n        }\n        \n        public void update(int start, int end, int height) {\n            for (int pos = start; pos <= end; pos++) {\n                update(pos, height, root);\n            }\n        }\n        \n        private void update(int point, int height, SegmentTreeNode curr) {\n            if (curr.start == curr.end) {\n                curr.val = height;\n                return;\n            }\n            \n            int mid = curr.getMid();\n            if (point <= mid) {\n                update(point, height, curr.left);\n            } else {\n                update(point, height, curr.right);\n            }\n            \n            curr.val = Math.max(curr.left.val, curr.right.val);\n        }\n        \n        public int query(int start, int end) {\n            return query(start, end, root);\n        }\n        \n                \n        private int query(int start, int end, SegmentTreeNode curr) {\n            if (curr.start == curr.end) {\n                return curr.val;\n            } else if (curr.start == start && curr.end == end) {\n                return curr.val;\n            } else {\n                int mid = curr.getMid();\n                if (start >= mid + 1) {\n                    return query(start, end, curr.right);\n                } else if (mid >= end) {\n                    return query(start, end, curr.left);\n                } else {\n                    int leftVal = query(start, mid, curr.left);\n                    int rightVal = query(mid + 1, end, curr.right);\n                    return Math.max(leftVal, rightVal);\n                }\n            }\n        }\n        \n        \n        class SegmentTreeNode {\n            int start;\n            int end;\n            int val;\n            SegmentTreeNode left;\n            SegmentTreeNode right;\n            \n            public SegmentTreeNode(int start, int end) {\n                this.start = start;\n                this.end = end;\n                this.val = 0;\n                if (start != end) {\n                    int mid = getMid();\n                    this.left = new SegmentTreeNode(start, mid);\n                    this.right = new SegmentTreeNode(mid + 1, end);\n                } \n            }\n            \n            public int getMid() {\n                return start + (end - start) / 2;\n            }\n                        \n        }\n    }\n}\n```\n\n**Compressed Co-ordinates (AC)**\nWe see that the actual number of points << range of points.\nThis is a hint that we can compress the range.\n\n```\nclass Solution {\n    public List<Integer> fallingSquares(int[][] positions) {\n        Map<Integer, Integer> index = getCompressedCoordinates(positions);\n        SegmentTree sg = new SegmentTree(index.size() + 1);\n        int maxHeight = 0;\n        List<Integer> output = new ArrayList<>();\n        \n        for (int[] position: positions) {\n            int start = index.get(position[0]);\n            int end = index.get(position[0] + position[1] - 1);\n            int heightInRange = sg.query(start, end);\n            int updatedHeightInRange = heightInRange + position[1];\n            maxHeight = Math.max(maxHeight, updatedHeightInRange);\n            output.add(maxHeight);\n            sg.update(start, end, updatedHeightInRange);\n        }\n        \n        return output;\n        \n    }\n    \n    private Map<Integer, Integer> getCompressedCoordinates(int[][] positions) {\n        Set<Integer> coords = new HashSet();\n        coords.add(0);\n        for (int[] pos: positions) {\n            coords.add(pos[0]);\n            coords.add(pos[0] + pos[1] - 1);\n        }\n        List<Integer> sortedCoords = new ArrayList(coords);\n        Collections.sort(sortedCoords);\n\n        Map<Integer, Integer> index = new HashMap();\n        int t = 0;\n        for (int coord: sortedCoords) index.put(coord, t++);\n        return index;\n    }\n    \n    class SegmentTree {\n        SegmentTreeNode root;\n        \n        public SegmentTree(int endIndex) {\n            root = new SegmentTreeNode(0, endIndex);\n        }\n        \n        public void update(int start, int end, int height) {\n            SegmentTree debug = this;\n            for (int pos = start; pos <= end; pos++) {\n                update(pos, height, root);\n            }\n        }\n        \n        private void update(int point, int height, SegmentTreeNode curr) {\n            if (curr.start == curr.end) {\n                curr.val = height;\n                return;\n            }\n            \n            int mid = curr.getMid();\n            if (point <= mid) {\n                update(point, height, curr.left);\n            } else {\n                update(point, height, curr.right);\n            }\n            \n            curr.val = Math.max(curr.left.val, curr.right.val);\n        }\n        \n        public int query(int start, int end) {\n            SegmentTree debug = this;\n            return query(start, end, root);\n        }\n        \n                \n        private int query(int start, int end, SegmentTreeNode curr) {\n            if (curr.start == 0 && curr.end == 2) {\n                int debug = 1;\n            }\n            if (curr.start == curr.end) {\n                return curr.val;\n            } else if (curr.start == start && curr.end == end) {\n                return curr.val;\n            } else {\n                int mid = curr.getMid();\n                if (start >= mid + 1) {\n                    return query(start, end, curr.right);\n                } else if (mid >= end) {\n                    return query(start, end, curr.left);\n                } else {\n                    int leftVal = query(start, mid, curr.left);\n                    int rightVal = query(mid + 1, end, curr.right);\n                    return Math.max(leftVal, rightVal);\n                }\n            }\n        }\n        \n        class SegmentTreeNode {\n            int start;\n            int end;\n            int val;\n            SegmentTreeNode left;\n            SegmentTreeNode right;\n            \n            public SegmentTreeNode(int start, int end) {\n                this.start = start;\n                this.end = end;\n                this.val = 0;\n                if (start != end) {\n                    int mid = getMid();\n                    this.left = new SegmentTreeNode(start, mid);\n                    this.right = new SegmentTreeNode(mid + 1, end);\n                } \n            }\n            \n            public int getMid() {\n                return start + (end - start) / 2;\n            }\n            \n        }\n    }\n}\n```\n\n**Lazy Propagation (AC)**\n\nThis isn\'t as hard as it looks and it makes range updates much faster.\nYou are unlikely to need to code this end to end in an interview, but it is helpful to understand how the lazy function works and when we propagate it to the lower levels.\n\n```\nclass Solution {\n    public List<Integer> fallingSquares(int[][] positions) {\n        Map<Integer, Integer> index = getCompressedCoordinates(positions);\n        SegmentTree sg = new SegmentTree(index.size() + 1);\n        int maxHeight = 0;\n        List<Integer> output = new ArrayList<>();\n        \n        for (int[] position: positions) {\n            int start = index.get(position[0]);\n            int end = index.get(position[0] + position[1] - 1);\n            int heightInRange = sg.query(start, end);\n            int updatedHeightInRange = heightInRange + position[1];\n            maxHeight = Math.max(maxHeight, updatedHeightInRange);\n            output.add(maxHeight);\n            sg.update(start, end, updatedHeightInRange);\n        }\n        \n        return output;\n        \n    }\n    \n    private Map<Integer, Integer> getCompressedCoordinates(int[][] positions) {\n        Set<Integer> coords = new HashSet();\n        coords.add(0);\n        for (int[] pos: positions) {\n            coords.add(pos[0]);\n            coords.add(pos[0] + pos[1] - 1);\n        }\n        List<Integer> sortedCoords = new ArrayList(coords);\n        Collections.sort(sortedCoords);\n\n        Map<Integer, Integer> index = new HashMap();\n        int t = 0;\n        for (int coord: sortedCoords) index.put(coord, t++);\n        return index;\n    }\n    \n    class SegmentTree {\n        SegmentTreeNode root;\n        \n        public SegmentTree(int endIndex) {\n            root = new SegmentTreeNode(0, endIndex);\n        }\n        \n        public void update(int start, int end, int height) {\n            SegmentTree debug = this;\n            for (int pos = start; pos <= end; pos++) {\n                update(pos, height, root);\n            }\n        }\n        \n        private void update(int point, int height, SegmentTreeNode curr) {\n            if (curr.start == curr.end) {\n                curr.val = height;\n                return;\n            }\n            \n            int mid = curr.getMid();\n            if (point <= mid) {\n                update(point, height, curr.left);\n            } else {\n                update(point, height, curr.right);\n            }\n            \n            curr.val = Math.max(curr.left.val, curr.right.val);\n        }\n        \n        public int query(int start, int end) {\n            SegmentTree debug = this;\n            return query(start, end, root);\n        }\n        \n                \n        private int query(int start, int end, SegmentTreeNode curr) {\n            if (curr.start == 0 && curr.end == 2) {\n                int debug = 1;\n            }\n            if (curr.start == curr.end) {\n                return curr.val;\n            } else if (curr.start == start && curr.end == end) {\n                return curr.val;\n            } else {\n                int mid = curr.getMid();\n                if (start >= mid + 1) {\n                    return query(start, end, curr.right);\n                } else if (mid >= end) {\n                    return query(start, end, curr.left);\n                } else {\n                    int leftVal = query(start, mid, curr.left);\n                    int rightVal = query(mid + 1, end, curr.right);\n                    return Math.max(leftVal, rightVal);\n                }\n            }\n        }\n        \n        class SegmentTreeNode {\n            int start;\n            int end;\n            int val;\n            SegmentTreeNode left;\n            SegmentTreeNode right;\n            \n            public SegmentTreeNode(int start, int end) {\n                this.start = start;\n                this.end = end;\n                this.val = 0;\n                if (start != end) {\n                    int mid = getMid();\n                    this.left = new SegmentTreeNode(start, mid);\n                    this.right = new SegmentTreeNode(mid + 1, end);\n                } \n            }\n            \n            public int getMid() {\n                return start + (end - start) / 2;\n            }\n            \n        }\n    }\n}\n```
[]