Segment tree solution
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```\nstruct nums {\nint n1;\nint n2;         \n};\n\nstruct node {\nint n;    //size of node\nvector <nums> v2;    \nvector <int> suffixmax;    \n};\n\nclass Solution {\npublic:\n    vector<int> maximumSumQueries(vector<int>& nums1, vector<int>& nums2, vector<vector<int>>& queries) {\nint n,m,i,j,k,x,y;\nvector <int> v3;\n    n=nums1.size();\n    if(n==0)return v3 ;\n    vector <nums> v1(n);\n    for(i=0;i<n;i++){\n    v1[i].n1=nums1[i]; v1[i].n2=nums2[i]; \n    }\n   nums1.clear(); nums2.clear();     \nsort(v1.begin(),v1.end(),mysort);     \n\nvector <node*> segtree(4*n+1);        \n\nbuildtree(segtree,0,0,n-1,v1);\n// v1.clear();       \n        vector <int> ans;\nint pos;        \nfor(i=0;i<queries.size();i++){\n    x=queries[i][0]; y=queries[i][1];\n pos=lower_bound(v1.begin(),v1.end(),x,compareX)-v1.begin();    \n    if(pos>=n){ ans.push_back(-1); continue ;}\n k=query_tree(segtree,0,0,n-1,pos,n-1,y); \nans.push_back(k);   \n}        \n        return ans;\n        \n}\n    \nstatic bool mysort(nums a , nums b){\n    if(a.n1==b.n1)return a.n2<b.n2;\n    return a.n1<b.n1;   \n}    \n    \nstatic bool compareY(nums tmp, int y){\nreturn tmp.n2<y;    \n}\n    \nstatic bool compareX(nums tmp, int x){\nreturn tmp.n1<x;    \n}    \n    \nint query_tree(vector <node*> &segtree, int v, int tl, int tr,int l ,int r, int y){\n    \nif(tl==l && tr==r){\nint pos=lower_bound(segtree[v]->v2.begin(),segtree[v]->v2.end(),y,compareY)-segtree[v]->v2.begin();\nif(pos>=segtree[v]->n)return -1;\nreturn segtree[v]->suffixmax[pos];    \n}    \nint a,b;\nint m=(tl+tr)/2;    \nif(l<=m)\na=query_tree(segtree,2*v+1,tl,m,l,min(r,m),y);    else a=-1;\nif(r>m)    \nb=query_tree(segtree,2*v+2,m+1,tr,max(l,m+1),r,y); else b=-1;\n    \n    return max(a,b);\n}\n    \n\nnode* combine(node* a, node* b){\nnode* tmp= new node();\ntmp->n=a->n+b->n;    \nint i,j,k,m; m=tmp->n; \ni=0; j=0;\n    \nwhile(i<a->n && j<b->n){\nif(a->v2[i].n2<=b->v2[j].n2){ tmp->v2.push_back(a->v2[i]); i++; }\nelse     { tmp->v2.push_back(b->v2[j]); j++; }\n}    \nwhile(i<a->n){\n tmp->v2.push_back(a->v2[i]); i++; \n} \nwhile(j<b->n){\n tmp->v2.push_back(b->v2[j]); j++; \n}\n\nfor(i=0;i<m;i++)\ntmp->suffixmax.push_back(tmp->v2[i].n1+ tmp->v2[i].n2);    \n   \n    \nfor(i=m-2;i>=0;i--){\ntmp->suffixmax[i]=max(tmp->suffixmax[i],tmp->suffixmax[i+1]);\n    }\n \nreturn tmp;    \n    \n}\n    \n    \nvoid buildtree(vector <node*> &segtree, int v, int l, int r, vector <nums> &v1){\n  if(l==r){\n  node* tmp=new node();    \n  tmp->n=1; tmp->v2.push_back(v1[l]);     tmp->suffixmax.push_back(v1[l].n1+v1[l].n2); segtree[v]=tmp;\n      return;\n  }  \n int mid = (l+r)/2;\nbuildtree(segtree,2*v+1,l,mid,v1);    \nbuildtree(segtree,2*v+2,mid+1,r,v1);     \n\nsegtree[v]=combine(segtree[2*v+1],segtree[2*v+2]);    \n    \n return;   \n}    \n    \n    /*\n    static bool myfn(nums a , nums b){\n    if(a.n2==b.n2)return a.n1<b.n1;\n    return a.n2<b.n2;   \n}\n    */\n    \n};\n```
['C++']