Segment tree C++ and python
Intuition\nUse segment tree. Sort all the points by x value, also for each query sort them by x value. For each query, update the new values for all the feasibl
# Intuition\nUse segment tree. Sort all the points by x value, also for each query sort them by x value. For each query, update the new values for all the feasible key ys with new values (x + y) in a segment tree.\n\n# Approach\nJust segment tree.\nNote when using values as the keys we need to change them into a smaller range (say [0, n -1] or [1, n] etc.) and still keep the order/\n\n# Complexity\n- Time complexity:\nO(qlogq + (n + q) * logn)\n\n- Space complexity:\nO(n)\n\n# Code\nC++\n```\nclass Solution {\n     int query(const vector<int> &tree, int ind, int left, int right, int x, int y) {\n        if (left >= x && right <= y) {\n            return tree[ind];\n        }\n        const int mid = (left + right) >> 1;\n        int r = -1;\n        if (x <= mid) {\n            r = query(tree, ind << 1, left, mid, x, y);\n        }\n        if (y > mid) {\n            r = max(r, query(tree, (ind << 1) | 1, mid + 1, right, x, y));\n        } \n        return r;\n    }\n\n    void update(vector<int> &tree, int ind, int left, int right, int x, int y) {\n        tree[ind] = max(tree[ind], y);\n        if (left >= x && right <= x) {\n            return;\n        }\n        const int mid = (left + right) >> 1;\n        if (x <= mid) {\n            update(tree, ind << 1, left, mid, x, y);\n        } else {\n            update(tree, (ind << 1) | 1, mid + 1, right, x, y);\n        } \n    }\npublic:\n    vector<int> maximumSumQueries(vector<int>& nums1, vector<int>& nums2, vector<vector<int>>& queries) {\n        const int n = nums1.size();\n        map<int, int> all;\n        vector<pair<int, int>> v(n);\n        for (int i = 0; i < n; ++i) {\n            ++all[nums2[i]];\n            v[i] = {nums1[i], nums2[i]};\n        }\n        sort(v.begin(), v.end());\n        const int m = queries.size();\n        vector<int> ind(m);\n        for (int i = 0; i < m; ++i) {\n            ind[i] = i;\n            ++all[queries[i][1]];\n        }\n        sort(ind.begin(), ind.end(), [&](const int x, const int y) {\n            return queries[x][0] > queries[y][0];\n        });\n        int mv = 0;\n        for (auto& p : all) {\n            p.second = ++mv;\n        }\n        vector<int> tree(mv << 2, -1);\n        vector<int> r(m);\n        for (int i = 0, j = n - 1; i < m; ++i) {\n            for (; j >= 0 && v[j].first >= queries[ind[i]][0]; update(tree, 1, 1, mv, all[v[j].second], v[j].first + v[j].second), --j)\n            ;\n            r[ind[i]] = query(tree, 1, 1, mv, all[queries[ind[i]][1]], mv);\n        }\n        return r;\n    }\n};\n\n```\n\nPython3\n```\nclass Solution:\n    def query(self, tree: List[int], ind: int, left: int, right: int, x: int, y: int) -> int:\n        if left >= x and right <= y:\n            return tree[ind]\n        mid = (left + right) >> 1\n        r = -1\n        if x <= mid:\n            r = self.query(tree, ind << 1, left, mid, x, y)\n        if y > mid:\n            r = max(r, self.query(tree, (ind << 1) | 1, mid + 1, right, x, y))\n        return r\n\n    def update(self, tree: List[int], ind: int, left: int, right: int, x: int, y: int) -> None:\n        tree[ind] = max(tree[ind], y)\n        if left >= x and right <= x:\n            return\n        mid = (left + right) >> 1\n        if x <= mid:\n            self.update(tree, ind << 1, left, mid, x, y)\n        else:\n            self.update(tree, (ind << 1) | 1, mid + 1, right, x, y)\n\n    def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n        n = len(nums1)\n        all_nums = defaultdict(int)\n        v = [(nums1[i], nums2[i]) for i in range(n)]\n        for num in nums2:\n            all_nums[num] += 1\n        v.sort()\n        m = len(queries)\n        ind = [i for i in range(m)]\n        for query in queries:\n            all_nums[query[1]] += 1\n        ind.sort(key=lambda x: queries[x][0], reverse=True)\n        mv = 0\n        for key in sorted(all_nums.keys()):\n            mv += 1\n            all_nums[key] = mv\n        tree = [-1] * (mv << 2)\n        r = [0] * m\n        j = n - 1\n        for i in ind:\n            while j >= 0 and v[j][0] >= queries[i][0]:\n                self.update(tree, 1, 1, mv, all_nums[v[j][1]], v[j][0] + v[j][1])\n                j -= 1\n            r[i] = self.query(tree, 1, 1, mv, all_nums[queries[i][1]], mv)\n        return r\n\n\n```
['Python', 'C++', 'Python3']