Lazy propagation | Point compression | Python
Intuition\n Describe your first thoughts on how to solve this problem. \nRange update speaks segment tree.\n\n# Approach\n Describe your approach to solving the
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nRange update speaks segment tree.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n**Lazy propagation + Point compression**:\nUse max function instead of the regular addition function.\nAlso since the squares are going to be in an increasing order hence no need to worry about coming back and updating the parent. The parent will always be greater.\n\nPS: I am so proud of myself solving this on my first attempt, because this was my 1000th AC question and the hardest question I have solved on leetcode. Have a great day, cheers. :)\n\n# Complexity\n- Time complexity: $$O(nlogn)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nfrom math import inf\n\n\nclass LazySegmentTree:\n    def __init__(self, arr):\n        self.arr = arr\n        self.arr_size = len(arr)\n        self.size = 4 * self.arr_size\n        self.tree = [0] * self.size\n        self.lazy = [0] * self.size\n        self.build_tree(0, 0, self.arr_size - 1)\n\n    def left_child(self, node):\n        return 2 * node + 1\n\n    def right_child(self, node):\n        return 2 * node + 2\n\n    def build_tree(self, node, start, end):\n        if start == end:\n            self.tree[node] = self.arr[start]\n            return self.tree[node]\n        mid = (start + end) // 2\n        self.tree[node] = max(\n            self.build_tree(self.left_child(node), start, mid),\n            self.build_tree(self.right_child(node), mid + 1, end),\n        )\n        return self.tree[node]\n\n    def update_diff(self, index, diff):\n        self.update_helper(0, 0, self.arr_size - 1, index, index, diff)\n\n    def update_range(self, left, right, value):\n        self.update_helper(0, 0, self.arr_size - 1, left, right, value)\n\n    def update_helper(self, node, start, end, left, right, diff):\n        # Handle lazy propagation\n        if self.lazy[node] != 0:\n            self.tree[node] = max(self.tree[node], self.lazy[node])\n            if start != end:\n                self.lazy[self.left_child(node)] = self.lazy[node]\n                self.lazy[self.right_child(node)] = self.lazy[node]\n            self.lazy[node] = 0\n\n        if start > right or end < left or start > end:\n            return\n\n        if start >= left and end <= right:\n            self.tree[node] = diff\n            if start != end:\n                self.lazy[self.left_child(node)] = diff\n                self.lazy[self.right_child(node)] = diff\n            return\n\n        mid = (start + end) // 2\n        self.update_helper(self.left_child(node), start, mid, left, right, diff)\n        self.update_helper(self.right_child(node), mid + 1, end, left, right, diff)\n        self.tree[node] = max(\n            self.tree[self.left_child(node)], self.tree[self.right_child(node)]\n        )\n\n    def query(self, left, right):\n        return self.query_helper(0, 0, self.arr_size - 1, left, right)\n\n    def query_helper(self, node, start, end, left, right):\n        if self.lazy[node] != 0:\n            self.tree[node] = max(self.tree[node], self.lazy[node])\n            if start != end:\n                self.lazy[self.left_child(node)] = self.lazy[node]\n                self.lazy[self.right_child(node)] = self.lazy[node]\n            self.lazy[node] = 0\n        if start >= left and end <= right:\n            return self.tree[node]\n\n        if start > right or end < left:\n            return 0\n\n        mid = (start + end) // 2\n        return max(\n            self.query_helper(self.left_child(node), start, mid, left, right),\n            self.query_helper(self.right_child(node), mid + 1, end, left, right),\n        )\n\n\n\nclass Solution:\n    def fallingSquares(self, positions):\n        ans = []\n        pos = set()\n        for l, side in positions:\n            pos.add(l)\n            pos.add(l + side - 1)\n        pos = sorted(list(pos))\n        mp = {}\n        for i, j in enumerate(pos):\n            mp[j] = i\n        n = len(pos)\n        st = LazySegmentTree([0] * n)\n        for l, side in positions:\n            left, right = mp[l], mp[l + side - 1]\n            mx = st.query(left, right)\n            st.update_range(left, right, mx + side)\n            ans.append(st.query(0, n - 1))\n        return ans\n\n\n# S = Solution()\n# print(S.fallingSquares([[1, 2], [2, 3], [6, 1]]))\n# print(S.fallingSquares([[100, 100], [200, 100]]))\n\n```
['Segment Tree', 'Python3']