Seg Tree | Offline queries | Commented
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```python3 []\nclass Node:\n    def __init__(self, l: int, r: int):\n        self.l = l\n        self.r = r\n        if l == r:\n            self.value = -1\n        else:\n            mid = (l + r) // 2\n            self.left = Node(l, mid)\n            self.right = Node(mid + 1, r)\n            self.value = max(self.left.value, self.right.value)\n    \n    def find(self, l: int, r: int) -> int:\n        if self.l > r or self.r < l: return -1\n        elif l <= self.l and self.r <= r: return self.value\n        else:\n            return max(self.left.find(l, r), self.right.find(l, r))\n    \n    def update(self, idx: int, value):\n        if self.l > idx or self.r < idx: return \n        elif idx == self.l == self.r: \n            self.value = value\n        else:\n            self.left.update(idx, value)\n            self.right.update(idx, value)\n            self.value = max(self.left.value, self.right.value)\n        \nclass Solution:\n    def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n        # Naive - O(q * N)\n        # a0, a1, ..., an\n        # b0, b1, ..., bn\n        # Optimized idea - This is based on a standard approach where we have to sort queries. We need to somehow apply binary search for each query to get to O(NlogN), for this on one side we can sort based on nums1 to figure out the start of the range to look for the maximum and on the other side sort based on nums2 so we can only consider nums2s that are greater than y described by the query\n\n        N = len(nums1)\n        M = len(queries)\n        \n        # order according to nums1 \n        arr1 = [(nums1[i], nums2[i]) for i in range(N)]\n        arr1.sort()\n        # Take the nums2 from arr1, and sort in desc order so we can take down to a certain y.\n        arr2 = [(arr1[i][1], i) for i in range(N)]\n        arr2.sort(reverse=True)\n        # sort queries in order of y.\n        queries = [(queries[i][0], queries[i][1], i) for i in range(M)]\n        queries.sort(key=lambda q: q[1], reverse=True)\n        # Seg tree for range maximum.\n        root = Node(0, N - 1)\n        # answer for each queries\n        ans = [0] * M\n        i = j = 0\n        for x, y, idx in queries:\n            while j < N and arr2[j][0] >= y:\n                # activate these indexes\n                i = arr2[j][1]\n                root.update(i, arr1[i][0] + arr1[i][1])\n                j += 1\n            # find from arr1 which indexes onwards we can consider for range maximum based on x.\n            i = bisect_left(arr1, x, key=lambda a: a[0])\n            ans[idx] = root.find(i, N - 1)\n        return ans\n            \n\n```
['Python3']