Easy segment tree || c++ || coordinate compression
Explanation \nUse segment tree with coordinate compression. Sort all the points by x value, also for each query sort them by x value. For each query, update the
# Explanation \nUse segment tree with coordinate compression. 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. note that there can be atmost 10^5 distinct value so we can use coordinate compression to store y values using hashmap. \n\n# Code\n```\nclass Solution {\npublic:\n    \n    static bool cmp(pair<int, int> &a, pair<int, int> &b) {\n        if(a.first == b.first) return a.second > b.second;\n        return a.first > b.first;\n    }\n    \n    bool static cmp2(vector<int> &a, vector<int> &b) {\n        if(a[0] == b[0]) return a[1] > b[1];\n        return a[0] > b[0];\n    }\n    \n    void update(int nl, int nr, int tidx, int idx, int val, vector<int> &tree) {\n        if(nl == nr) {\n            tree[tidx] = max(val, tree[tidx]);\n            return; \n        }\n        \n        int mid = (nl+nr)/2; \n        if(idx <= mid) {\n            update(nl, mid, 2*tidx+1, idx, val, tree);\n        } else {\n            update(mid+1, nr, 2*tidx+2, idx, val, tree);\n        }\n        \n        tree[tidx] = max(tree[2*tidx+1], tree[2*tidx+2]);\n    }\n    \n    int query(int nl, int nr, int tidx, int l, int r, vector<int> &tree) {\n        if(nl > r or nr < l) return INT_MIN;\n        if(nl >= l and nr <= r) return tree[tidx];\n        \n        int mid = (nl+nr)/2;\n        int left = query(nl, mid, 2*tidx+1, l, r, tree);\n        int right = query(mid+1, nr, 2*tidx+2, l, r, tree);\n        \n        return max(left, right); \n    }\n    \n    \n    vector<int> maximumSumQueries(vector<int>& nums1, vector<int>& nums2, vector<vector<int>>& queries) {\n        vector<int> temp; \n        vector<pair<int, int>> v;\n        int n = nums1.size();\n        int m = queries.size();\n        \n        \n        unordered_map<int, int> mp; \n        \n        for(int i = 0; i < n; i++) {\n            temp.push_back(nums2[i]);\n            v.push_back({nums1[i], nums2[i]});\n        }\n        for(auto &q: queries) {\n            int y = q[1];\n            temp.push_back(y);\n        }\n        sort(temp.begin(), temp.end()); \n        sort(v.begin(), v.end(), cmp); \n        \n        int newVal = 0; \n        \n        for(int i = 0; i < temp.size(); i++) {\n            if(mp.find(temp[i]) != mp.end()) continue; \n            mp[temp[i]] = newVal++; \n        }\n        \n        int N = newVal+1;\n        vector<int> tree(4*N+1, -1);\n        \n        \n        for(int i = 0; i < m; i++) {\n            queries[i].push_back(i);\n        }\n        sort(queries.begin(), queries.end(), cmp2);\n        \n        vector<int> ans(m);\n\n        int j = 0; \n        for(int i = 0; i < m; i++){\n            \n            auto q = queries[i]; \n            int idx = q[2];\n            int x = q[0];\n            int y = q[1];\n            \n            \n            while(j < n and v[j].first >= x) {\n                int X = v[j].first;\n                int Y = v[j].second; \n                \n                int val = X+Y; \n                int index = mp[Y]; \n                \n                // cout<<i<<" "<<j<<" "<<val<<" "<<index<<endl;\n                \n                update(0, N-1, 0, index, val, tree); \n                j++; \n            }\n            \n            \n            int maxi = query(0, N-1, 0, mp[y], N, tree);\n            ans[idx] = maxi; \n        }\n        \n        \n        return ans;\n    }\n};\n```
['Segment Tree', 'C++']