C++ - Sorting + Binary Search + Binary Index tree
This is one of the hardes problem.\nUsed sort query and nums1 in descending order so we can start finding max element first and considered results for next time
This is one of the hardes problem.\nUsed sort query and nums1 in descending order so we can start finding max element first and considered results for next time. \nUsed Binary Index tree to find max values for nums2\n\n\n# Code\n```\nclass Solution {\n    void updateBit(int itIndex, int value,vector<int>& indexTree){\n        for(;itIndex<=indexTree.size()-1;itIndex += itIndex & (-itIndex)){\n            indexTree[itIndex] = max(indexTree[itIndex],value);\n        }\n    }\n    int queryBit(int itIndex,vector<int>& indexTree){\n        int ans=-1;\n        for(;itIndex>0;itIndex -= itIndex & (-itIndex)){\n            ans = max(indexTree[itIndex],ans);\n        }\n        return ans;\n\n    }\npublic:\n    vector<int> maximumSumQueries(vector<int>& nums1, vector<int>& nums2, vector<vector<int>>& queries) {\n        vector<int> num1Idx(nums1.size());\n        std::iota(begin(num1Idx),end(num1Idx),0);\n        sort(begin(num1Idx), end(num1Idx), [&](int a, int b){ return nums1[a] > nums1[b];});\n\n        vector<int> num2Idx(nums2.size());\n        iota(begin(num2Idx),end(num2Idx),0);\n        sort(begin(num2Idx), end(num2Idx), [&](int a, int b){ return nums2[a] > nums2[b];});\n        unordered_map<int,int> indexMap;\n        for (int i=0;i<num2Idx.size();i++) indexMap[num2Idx[i]]=i;\n        vector<int> indexTree(nums2.size()+1,-1);\n\n        vector<int> queriesIdx(queries.size());\n        iota(begin(queriesIdx),end(queriesIdx),0);\n        sort(begin(queriesIdx), end(queriesIdx), [&](int a, int b){ return queries[a][0] > queries[b][0];});\n        vector<int> ans(queries.size());\n\n        int n1=0,n2=0,num1I=0,v=0;\n        for(int i=0;i<queries.size();i++){\n            n1 = queries[queriesIdx[i]][0];\n            n2 = queries[queriesIdx[i]][1];\n            while (num1I<nums1.size() && nums1[num1Idx[num1I]]>=n1){\n                v = nums1[num1Idx[num1I]] + nums2[num1Idx[num1I]];\n                updateBit(indexMap[num1Idx[num1I]]+1,v,indexTree);\n                num1I++;\n            }\n            v = lower_bound(num2Idx.begin(),num2Idx.end(),n2,[&](auto& a, auto& b){\n                return nums2[a]>=b;\n            })-num2Idx.begin();\n            ans[queriesIdx[i]]=queryBit(v,indexTree);\n        }\n        return ans;\n    }\n};\n```
['C++']