Python Segment Tree with Lazy Propagation
http://www.geeksforgeeks.org/lazy-propagation-in-segment-tree/\n\n\nclass Solution:\n    def fallingSquares(self, positions):\n        """\n        :type positi
http://www.geeksforgeeks.org/lazy-propagation-in-segment-tree/\n\n```\nclass Solution:\n    def fallingSquares(self, positions):\n        """\n        :type positions: List[List[int]]\n        :rtype: List[int]\n        """\n        # compress positions into consecutive indices\n        all_pos = set()\n        for p in positions:\n            all_pos.add(p[0])\n            all_pos.add(p[0] + p[1])\n        \n        pos_ind = {}\n        for i, pos in enumerate(sorted(all_pos)):\n            pos_ind[pos] = i\n        \n        n = len(pos_ind)\n        segtree = [0] * (4 * n)\n        lazy = [0] * (4 * n)\n        \n        def _insert(left, right, h, root, start, end):\n            if lazy[root] != 0:\n                if start != end:\n                    lazy[root*2] = max(lazy[root*2], lazy[root])\n                    lazy[root*2 + 1] = max(lazy[root*2+1], lazy[root])\n                segtree[root] = max(segtree[root], lazy[root])\n                lazy[root] = 0          \n            \n            if left > end or right < start:\n                return\n            \n            if start == end:\n                segtree[root] = max(segtree[root], h)\n                return \n            \n            if left <= start and right >= end:\n                segtree[root] = max(segtree[root], h)\n                lazy[root*2] = max(lazy[root*2], h)\n                lazy[root*2 + 1] = max(lazy[root*2+1], h)\n                return\n            \n            mid = (start + end) // 2\n            _insert(left, right, h, root*2, start, mid)\n            _insert(left, right, h, root*2 + 1, mid + 1, end)\n            segtree[root] = max(segtree[2*root], segtree[2*root + 1], h)\n            return\n        \n        def _query(left, right, root, start, end):\n            if lazy[root] != 0:\n                if start != end:\n                    lazy[root*2] = max(lazy[root*2], lazy[root])\n                    lazy[root*2 + 1] = max(lazy[root*2+1], lazy[root])\n                segtree[root] = max(segtree[root], lazy[root])\n                lazy[root] = 0\n                \n            if left > end or right < start:\n                return 0\n            \n            if start == end: \n                return segtree[root]\n            \n            if left <= start and right >= end:\n                return segtree[root]\n            \n            mid = (start + end) // 2\n            return max(_query(left, right, root*2, start, mid), _query(left, right, root*2+1, mid + 1, end))\n        \n        def insert(left, right, h):\n            _insert(left, right, h, 1, 0, n-1)\n        \n        def query(left, right):\n            return _query(left, right, 1, 0, n-1)\n        \n        res = []\n        accu_max = 0\n        for p in positions:\n            left_raw, h = p\n            right_raw = left_raw + h\n            left = pos_ind[left_raw]\n            right = pos_ind[right_raw] - 1\n            cur_max = query(left, right)\n            new_max = cur_max + h\n            accu_max = max(accu_max, new_max)\n            res.append(accu_max)\n            insert(left, right, new_max)\n        return res\n```
[]