[Python] Segment Tree with LP
Idea: Denote N = number of squares; create 2 * N lines corresponding to left and right edges of every squares. These 2 * N lines define our 2 * N segments. Segm
**Idea:** Denote N = number of squares; create 2 * N lines corresponding to left and right edges of every squares. These 2 * N lines define our 2 * N segments. Segment Tree serve to provide height of each segment.\nFor each incoming square, we use binary search to find its left edge and right edge, and update the height of corresponding segment. Update rule here is: new segment height = maximum old height of any point in segment + square side. Or in formula: <code>h(i, j) = max{ h(k, k) } + side</code> where <code> k in [i, j]</code>. We can query the segment tree to find <code>max{h(k, k)} </code> in <code>O(logN)</code>. Update the height in <code>O(logN)</code>. And finally we query the 0-th element of segment tree to find maximum height, this is also done in O(logN).\n\nThus overall time complexity is <code>O(NlogN)</code>. Auxiliary space is <code>O(N)</code>.\n```\nclass SegmentTree:\n    def __init__(self, N):\n        self.N = N\n        self.st = [0] * 4 * N\n        self.lazy = [0] * 4 * N\n    def updateLazy(self, index, val, low, high):\n        self.st[index] = val\n        if low != high:\n            self.lazy[2*index + 1] = val\n            self.lazy[2*index + 2] = val\n        self.lazy[index] = 0\n    def updateRange(self, index, i, j, val, low, high):\n        if low > j or high < i: \n            return\n        if self.lazy[index]:\n            self.updateLazy(index, self.lazy[index], low, high)\n        if i <= low and high <= j:\n            self.updateLazy(index, val, low, high)\n            return\n        mid = (low + high)//2\n        self.updateRange(2*index + 1, i, j, val, low, mid)\n        self.updateRange(2*index + 2, i, j, val, mid + 1, high)\n        self.st[index] = max(self.st[2*index + 1], self.st[2*index + 2])\n    def queryRange(self, index, i, j, low, high):\n        if low > j or high < i:\n            return 0\n        if self.lazy[index]:\n            self.updateLazy(index, self.lazy[index], low, high)\n        if i <= low and high <= j:\n            return self.st[index]\n        mid = (low + high)//2\n        left = self.queryRange(2*index + 1, i, j, low, mid)\n        right = self.queryRange(2*index + 2, i, j, mid + 1, high)\n        return max(left, right)\n        \nclass Solution:\n    def fallingSquares(self, positions: List[List[int]]) -> List[int]:\n        lines = []\n        n = len(positions)\n        for pos in positions:\n            lines.append(pos[0])\n            lines.append(pos[0] + pos[1])\n        lines = sorted(lines)\n        st = SegmentTree(2*n)\n        res = []\n        for pos in positions:\n            start_idx = bisect.bisect_right(lines, pos[0])\n            end_idx = bisect.bisect_left(lines, pos[0] + pos[1])\n            maxHeight = st.queryRange(0, start_idx, end_idx, 0, 2*n - 1)\n            st.updateRange(0, start_idx, end_idx, pos[1] + maxHeight, 0, 2*n - 1)\n            res.append(st.st[0])\n        return res\n```
[]