Fenwick Tree + Sorting (C++)
Intuition\n Describe your first thoughts on how to solve this problem. \nBase on this solution, but I use Binary Indexed Tree rather than Segment Tree to solve 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nBase on [this solution](https://leetcode.com/problems/maximum-sum-queries/solutions/3625840/segment-tree-coordinate-compression-sorting-c/), but I use Binary Indexed Tree rather than Segment Tree to solve RMQ(Range Minimum/Maximum Query) problem.\n\nIf you want to use BIT to solve the RMQ problem, there is an important point to note. When updating the values, if you want to compute the maximum, the value can only be increased, and if you want to compute the minimum, the value can only be decreased.\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: $$O(n*logn)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n- Space complexity: $$O(n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Time complexity about use Fenwick Tree to solve RMQ problem\n- update: $$O(logn)$$\n- query: $$O(logn)$$\n \n# Code\nC++\n```\nclass Solution {\npublic:\n    vector<int> BIT, arr; // 1-indexed\n    void update(int idx, int val){ // update arr[idx] = val\n        arr[idx] = val;\n        for(int i=idx;i<BIT.size();i+=i&-i)\n            BIT[i] = max(BIT[i], val);\n    }\n    int query(int l, int r){ // query maximum value in arr[l...r]\n        int ans = -1;\n        for(int i=r;i>=l;){\n            if(i - (i&-i) < l){\n                ans = max(ans, arr[i]);\n                i--;\n            }\n            else {\n                ans = max(ans, BIT[i]);\n                i-=i&-i;\n            }\n        }\n        return ans;\n    }\n    vector<int> maximumSumQueries(vector<int>& nums1, vector<int>& nums2, vector<vector<int>>& queries) {\n        int n = nums1.size();\n        vector<pair<int, int> > nums(n);\n        for(int i=0;i<n;i++)\n            nums[i] = {nums1[i], nums2[i]};\n        sort(nums.begin(), nums.end());\n\n        vector<pair<pair<int, int>, int> > pvec(queries.size());\n        for(int i = 0;i<queries.size();i++)\n            pvec[i] = {{queries[i][0], queries[i][1]}, i};\n        sort(pvec.begin(), pvec.end(), greater<pair<pair<int, int>, int> >());\n\n        map<int, int> mp;\n        for(int i=0;i<n;i++)\n            mp[nums2[i]]++;\n        for(int i=0;i<queries.size();i++)\n            mp[queries[i][1]]++;\n        \n        int i = 1;\n        for(auto &it: mp)\n            it.second = i++;\n\n        int sz = mp.size();  \n        BIT.clear();\n        BIT.resize(sz+1, -1);\n        arr.clear();\n        arr.resize(sz+1, -1);\n\n        vector<int> ans(queries.size());\n        int index = n-1;\n        for(auto &[p, idx]: pvec){\n            \n            while(index>=0 && nums[index].first>=p.first){\n                int ind = mp[nums[index].second], sum = nums[index].first + nums[index].second;\n                if(query(ind, ind) < sum)\n                    update(ind, sum);\n                index--;\n            }\n\n            ans[idx] = query(mp[p.second], sz);\n        }\n        return ans;\n    }\n};\n```
['Binary Indexed Tree', 'Sorting', 'C++']