Simple and short version of segment tree with lazy update
Intuition\n Describe your first thoughts on how to solve this problem. \nI found the segment tree in the solutions are very long so that I update one with short
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nI found the segment tree in the solutions are very long so that I update one with short version. you can also change my segment tree code into template (I did so, lol).\n\nNOTE: when you want to use segment tree to solve other questions, remember update the max() part in LazySegmentTree\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n- step1: query current result in the range\n- step2: add the new one\n- step3: update the tree\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```python3 []\nclass LazySegmentTree:\n\n    def __init__(self):\n        self.vals = Counter()\n        self.lazy = Counter()\n\n\n    def query(self, start, end, left, right, index):\n        if start > right or end < left:\n            return 0\n\n        if start <= left <= right <= end:\n            return self.vals[index]\n\n        mid = (left + right) // 2\n        left_value = self.query(start, end, left, mid, 2 * index)\n        right_value = self.query(start, end, mid + 1, right, 2 * index + 1)\n        return max(self.lazy[index], left_value, right_value)\n\n    def update(self, start, end, left, right, index, value = 1):\n        if start > right or end < left:\n            return\n\n        if start <= left and right <= end:\n            self.vals[index] = max(self.vals[index], value)\n            self.lazy[index] = max(self.lazy[index], value)\n        else:\n            mid = (left + right) // 2\n            self.update(start, end, left, mid, index * 2, value)\n            self.update(start, end, mid + 1, right, index * 2 + 1, value)\n\n            self.vals[index] = max(self.lazy[index],\n                self.vals[index * 2], self.vals[index * 2 + 1]\n            )\n\n\n\n\nclass Solution:\n    def fallingSquares(self, positions):\n\n\n        sg_tree = LazySegmentTree()\n        res = []\n        res_max = 0\n        for start, length in positions:\n            end = start + length - 1\n            current = sg_tree.query(start, end, 0, 10**9, 1)\n            current_new = current + length\n            \n            sg_tree.update(start, end, 0, 10**9, 1, current_new)\n\n            res_max = max(res_max, current_new)\n            res.append(res_max)\n\n        return res\n\n\n\n\n```
['Segment Tree', 'Python3']