segment tree
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\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```\n#from 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        mid = (start + end) // 2\n        if start == mid == end:      #.              |\n            self.tree[node] = self.arr[start] #.   sme\n            return self.tree[node]\n      \n\n        if start <= mid and       start and mid < end or start+1 == end: # start != end:  #. |    |.  #   |.  |.   |\n            self.tree[node] = max(                                      #                    sm.  e.  #   s   m.   e\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\n        mid = (start + end) // 2\n\n\n        if self.lazy[node] != 0:\n            self.tree[node] = max(self.tree[node], self.lazy[node])\n            if start <= mid and       start and mid < end or start+1 == end :  # start != end:  #. |    |.  #   |.  |.   |\n                self.lazy[self.left_child(node)] = self.lazy[node]                    #           sm.   e  #.  s.  m.   e\n                self.lazy[self.right_child(node)] = self.lazy[node]\n            \n            if start == mid == end: ###.  |\n                self.lazy[node] = 0  #.  sme\n                                                        #.  l   r  >  s.  e.  #.    s.  e  <   l.  r\n        if start > right or end < left or start > end:  #.  |___|.    |___|.  #.    |___|.     |___|. \n            return                                       #  \n                                          #.              l|___|r       #        l|___|r        #.        l|_______|r.     #.        l|___|r\n        if start >= left and end <= right:   #            s|_______|e.  #    s|_______|e.       #.        s|_______|e.     #.     s|_________|e.\n            self.tree[node] = diff\n            if   start < end and mid < end  and start <= mid or start+1 == end :# start != end:   # #. |    |.  #    |.  |.   |\n                self.lazy[self.left_child(node)] = diff                         #                      sm.  e.  #.   s.  m.   e\n                self.lazy[self.right_child(node)] = diff\n            return\n\n       \n        if self.lazy[node] == 0:   # xxxx   \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        \n        mid = (start + end) // 2\n        \n        if self.lazy[node] != 0:\n            self.tree[node] = max(self.tree[node], self.lazy[node])\n            \n            if start <= mid and       start and mid < end or start+1 == end : # start != end: # #. |    |.  #    |.  |.   |\n                self.lazy[self.left_child(node)] = self.lazy[node]                        #        sm.  e   #.   s.  m.   e\n                self.lazy[self.right_child(node)] = self.lazy[node]\n            \n            if  start <= mid <= end:  ####.           |\n                self.lazy[node] = 0   #              sme\n\n        if left <= start  and end <= right:  #.        l|___|r       #        l|___|r    #.        l|_______|r.     #.        l|___|r\n            return self.tree[node]           #         s|_______|e.  #    s|_______|e.   #.        s|_______|e.     #.     s|_________|e.\n\n        if start > right or end < left:\n            return 0\n\n        \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(object):\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\nS = Solution()\nprint(S.fallingSquares([[1, 2], [2, 3], [6, 1]]))\nprint(S.fallingSquares([[100, 100], [200, 100]]))\n\n"""\n[2, 5, 5]\n[100, 100]\n"""\n```
['Python']