bounding queries
Intuition\nWe need to convert bounds on both array such that they are accessible by binary search which seems valid optimization for range queries \n\n# Approac
# Intuition\nWe need to convert bounds on both array such that they are accessible by binary search which seems valid optimization for range queries \n\n# Approach\ndata is in form\nx . . . . . .\ny . . . . . .\n\nnow to work on bound with x we need to sort both arrays according to x we will get  ...... (1)\nx1 x2 .... xn\ny . . . . . .\n\n\nnow to work on bound on y we will take suffix maxima that will tell that what is best Y we can have from index (i to end),using this we can find till which index we need to look for solution such that y >= required\nx1 x2 ..... xn\nyn ......y2 y1    (taking cumulative  maximum  from index n towards index 1 will sort it in reverse order that\'s why indexed like this) \n\n\nnow for query we\'ll find first x that is >= queryX (indexX)   (it must be clear that this X bound is correct as x is sorted so every values >= queryX will have correct value of X)\n \nfind first y from end which is >= queryY (indexY)  ( this Y bound is correct because any index > indexY will have lower y values then required so none of our concern for our query) \n\nIt must be clear that 1 possible solution is indexY , since nums1[indexY] + suffixSum[indexY] are equivalent to (nums1[i] + nums2[i])\n  now taking max sum in range (indexX,indexY)  in data (1) will give us solution for give range. \n\n\ntest RUN \ninitial arrays \n[]\n\n\n# Proof why it\'s correct:\nthis is correct because as we said 1 possible solution is indexY which is upper bound of our solution means it has max possible x with a valid value of y (as we need max sum num1[i] + num2[i] this is nums2[i] == suffixMaxima as this values has occured for first time from ending till this index)\n\nnow any other x in lower range with smaller y (< required) will never be solution\nsince x is already smaller and if y is also smaller than one and indexY it\'s sum is going to be smaller\n\nso taking maxSum will either converge to indexY or will give best solution in bound\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Each query taking logN time so complete NlogN\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n# Code\n```\nconst int MAXN = 1e5 + 5; \nclass Solution {\n    // creating segment tree \n    int t[4*MAXN];\n    int sum(int v, int tl, int tr, int l, int r) {\n        if (l > r) \n            return 0;\n        if (l == tl && r == tr) {\n            return t[v];\n        }\n        int tm = (tl + tr) / 2;\n        return max(sum(v*2, tl, tm, l, min(r, tm)),sum(v*2+1, tm+1, tr, max(l, tm+1), r));\n    }\n    void build(vector<int> &a, int v, int tl, int tr) {\n        if (tl == tr) {\n            t[v] = a[tl];\n        } else {\n            int tm = (tl + tr) / 2;\n            build(a, v*2, tl, tm);\n            build(a, v*2+1, tm+1, tr);\n            t[v] = max(t[v*2], t[v*2+1]);\n        }\n    }\n\n    // finding range queries \n    int solve(int x,int y,vector<int> &xx,vector<int> &yy){\n        int l = lower_bound(xx.begin(),xx.end(),x) - xx.begin(); \n        // finding first index where suffix maxima is >= y from ending of array \n        int r = lower_bound(yy.rbegin(),yy.rend(),y) - yy.rbegin();  \n        // converting index from end to index from start like index from end = 0 means it\'s last element from begining \n        r = xx.size() - r - 1; \n        // getting range query result as per requirement \n        if(l <= r){\n            return sum(1,0,xx.size()-1,l,r); \n        }\n        return -1;\n    }\npublic:\n    vector<int> maximumSumQueries(vector<int>& nums1, vector<int>& nums2, vector<vector<int>>& queries) {\n        int n = nums1.size(); \n        int m = queries.size(); \n\n        // sorting in accordance to nums1 \n        vector<int> ids(n); \n        iota(ids.begin(),ids.end(),0); \n        sort(ids.begin(),ids.end(),[&](int i,int j){\n            return (nums1[i] < nums1[j]);\n        });\n        sort(nums1.begin(),nums1.end()); \n        \n        // taking suffMaxima in sorted array \n        vector<int> suffMaxima(n); \n        suffMaxima.back() = nums2[ids.back()]; \n        for(int i=n-2;i>=0;i-=1){\n            suffMaxima[i] = max(suffMaxima[i+1],nums2[ids[i]]); \n        }\n        \n        // taking sum of sorted array and inserting it in segment tree to make range queries \n        vector<int> sm(n);\n        for(int i=0;i<n;i+=1){\n            sm[i] = (nums1[i] + nums2[ids[i]]); \n        }\n        build(sm,1,0,n-1); \n        \n        // computing solution for each query \n        vector<int> sol;\n        for(auto &q: queries){\n            sol.push_back(solve(q[0],q[1],nums1,suffMaxima)); \n        }\n        return sol; \n    }\n};\n```
['Binary Search', 'Segment Tree', 'Prefix Sum', 'C++']