Python (dynamic) segment tree with Lazy-Propagation O(NLogN)
I find solution 4 a little confusing. I have implemented a dynamic segment tree with Lazy-Propagation, inspired by @luxy622:\n\nfrom collections import defaultd
I find solution 4 a little confusing. I have implemented a dynamic segment tree with Lazy-Propagation, inspired by [@luxy622:](https://leetcode.com/problems/my-calendar-iii/discuss/214831/Python-13-Lines-Segment-Tree-with-Lazy-Propagation-O(1)-time)\n```\nfrom collections import defaultdict\nclass Solution:\n    def query(self, start, end, left, right, ID):\n        if right<start or left>end or left>right:\n            return 0\n        if left>=start and right<=end:\n            return self.tree[ID]\n        else:\n            mid = (left+right)//2\n            return max(self.lazy[ID], max(self.query(start, end, left, mid, 2*ID), self.query(start, end, mid+1, right, 2*ID+1)))\n\n    def update(self, start, end, left, right, ID, height):\n        if right<start or left>end or left>right:\n            return\n        if left>=start and right<=end:\n            self.tree[ID] = max(height, self.tree[ID])\n            self.lazy[ID] = max(height, self.lazy[ID])\n        else:\n            mid = (left+right)//2\n            self.update(start, end, left, mid, 2*ID, height)\n            self.update(start, end, mid+1, right, 2*ID+1, height)\n            self.tree[ID] = max(self.lazy[ID], max(self.tree[2*ID], self.tree[2*ID+1]))\n    \n    def fallingSquares(self, positions: List[List[int]]) -> List[int]:\n        coords = set()\n        for left, size in positions:\n            coords.add(left)\n            coords.add(left + size - 1)\n        index = {x: i for i, x in enumerate(sorted(coords))}\n        best = 0\n        res = []\n        self.tree = defaultdict(int)\n        self.lazy = defaultdict(int)\n        for pos in positions:\n            x, y = index[pos[0]], index[pos[0] + pos[1] - 1]\n            h = pos[1] + self.query(x, y, 0, len(index), 1)\n            best = max(h, best)\n            self.update(x, y, 0, len(index), 1, h)\n            res.append(best)\n        return res\n```
['Tree']