EASY TO UNDERSTAND SEGMENT TREE + QUERY OFFLINE
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\nFor each query sort it in the order such that the biggest query comes fir
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\nFor each query sort it in the order such that the biggest query comes first(i.e. one with the greatest value of xi and yi).\nSort the pair of {nums1[i],nums2[i]} in the same order.\n\nThen for query {xi,yi} put all the values whose nums1 val is greater than xi in the segment tree.\n\nWhat value am I talking about? Naturally its the sum of nums1+nums2.\nEach index of the segment tree corresponds to the compressed value of nums2.\n\nAfter you can simply query in the range of yi to the maximum value available.(Note: here I am talking about compressed values).\n\nDo upvote if you liked this solution.\n\n# Code\n```\nclass Solution {\npublic:\nstatic bool cmp(vector<int> &a,vector<int> &b){\n    if(a[0]==b[0]){\n        return a[1]>b[1];\n    }\n    else{\n        return a[0]>b[0];\n    }\n}\n#define ll long long\n\nvector<ll> t;\n\n\nvoid build(ll ind,ll l,ll r){\n    if(l==r){\n        t[ind]=-1;\n        return;\n    }\n    ll mid=(l+r)/2;\n    build(ind*2,l,mid);\n    build(ind*2+1,mid+1,r);\n    t[ind]=max(t[2*ind],t[2*ind+1]);\n}\n\nvoid update(ll index,ll l,ll r,ll pos,ll val){\n    if(pos<l || pos>r)return;\n\n    if(l==r){\n        t[index]=max(t[index],val);\n        return;\n    }\n    ll mid=(l+r)/2;\n    update(2*index,l,mid,pos,val);\n    update(2*index+1,mid+1,r,pos,val);\n    t[index]=max(t[2*index],t[2*index+1]);\n\n}\n\nll query(ll index, ll l, ll r, ll lq, ll rq) {\n    if (l > rq || lq > r) {\n        return -1;\n    }\n    if (lq <= l && r <= rq) {\n        return t[index];\n    }\n    ll mid = (l + r) / 2;\n    return max(query(2 * index, l, mid, lq, rq), query(2 * index + 1, mid + 1, r, lq, rq));\n}\n\n    vector<int> maximumSumQueries(vector<int>& nums1, vector<int>& nums2, vector<vector<int>>& queries) {\n        map<int,int> m;\n        for(auto i:nums2){\n            m[i];\n        }\n        for(auto i:queries){\n            m[i[1]];\n        }\n        int n=nums1.size();\n        int cnt=0;\n        for(auto &i:m){\n            i.second=cnt++;\n        }     //index compression\n        t.resize(4*cnt+4);\n        vector<vector<int>> a,q;\n        for(int i=0;i<n;i++){\n            a.push_back({nums1[i],nums2[i]});\n        }\n        sort(a.begin(),a.end(),cmp);\n        \n        for(int i=0;i<queries.size();i++){\n            q.push_back({queries[i][0],queries[i][1],i});\n        }\n        int ind=0;\n        int d=q.size();\n        vector<int> ans(d,-1);\n        sort(q.begin(),q.end(),cmp);\n        build(1,0,cnt+1);\n        for(auto i:q){\n\n            while(ind<n && a[ind][0]>=i[0]){\n                update(1,0,cnt+1,m[a[ind][1]],a[ind][0]+a[ind][1]);\n                ind++;\n            }\n            ll res=query(1,0,cnt+1,m[i[1]],cnt+1);\n            ans[i[2]]=res;\n        }\n        return ans;\n    }\n};\n```
['Segment Tree', 'C++']