Merge Sort Segment Tree
IntuitionAs we can see it is asking us to do range queries so segment tree comes to mind and since it is asking us to do array operation (lower bound) so we nee
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
As we can see it is asking us to do range queries so segment tree comes to mind and since it is asking us to do array operation (lower bound) so we need to have array also i.e. merge sort tree.
# Approach
<!-- Describe your approach to solving the problem. -->
Our Segment Tree will have pair<vector<int>,vector<int>> as value of each node.
where first vector represents nums2 and second represents nums1[i] + nums2[i] suffix array for maximum operation.

# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
O(N(log n)^2)

- Space complexity:
O(N(log n)^2)
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```cpp []
class Solution {
public:
    pair<vector<int>, vector<int>> merge(pair<vector<int>, vector<int>> &v1, pair<vector<int>, vector<int>> &v2) {
        int i = 0, j = 0, k = 0;
        pair<vector<int>, vector<int>> v;
        v.first.resize(v1.first.size() + v2.first.size());
        v.second.resize(v1.first.size() + v2.first.size());
        
        while (i < v1.first.size() && j < v2.first.size()) {
            if (v1.first[i] > v2.first[j]) {
                v.first[k] = v2.first[j];
                v.second[k++] = v2.second[j++]; 
            } else {
                v.first[k] = v1.first[i];
                v.second[k++] = v1.second[i++]; 
            }
        }
        while (i < v1.first.size()) {
            v.first[k] = v1.first[i];
            v.second[k++] = v1.second[i++]; 
        }
        while (j < v2.first.size()) {            
            v.first[k] = v2.first[j];
            v.second[k++] = v2.second[j++];
        }
        int n = v.second.size();
        for (int i = n - 2; i >= 0; i--) {
            v.second[i] = max(v.second[i], v.second[i + 1]);
        }
        return v;
    }

    void build(int node, int l, int r, vector<pair<int, int>> &nums, vector<pair<vector<int>, vector<int>>> &segmentTree) {
        if (l == r) {
            segmentTree[node].first = {nums[l].second};
            segmentTree[node].second = {nums[l].first + nums[l].second};
            return; 
        }
        int mid = (l + r) / 2;
        build(2 * node + 1, l, mid, nums, segmentTree);
        build(2 * node + 2, mid + 1, r, nums, segmentTree);
        segmentTree[node] = merge(segmentTree[2 * node + 1], segmentTree[2 * node + 2]);
    }

    int query(int st, int en, int yi, int node, int l, int r, vector<pair<vector<int>, vector<int>>> &segmentTree) {
        if (st > r || l > en) return -1;
        if (st <= l && en >= r) {
            int j = lower_bound(segmentTree[node].first.begin(), segmentTree[node].first.end(), yi) - segmentTree[node].first.begin();
            if (j == segmentTree[node].first.size()) return -1;
            return segmentTree[node].second[j];
        }
        int mid = (l + r) / 2;
        return max(query(st, en, yi, 2 * node + 1, l, mid, segmentTree),
                   query(st, en, yi, 2 * node + 2, mid + 1, r, segmentTree));
    }

    vector<int> maximumSumQueries(vector<int> &nums1, vector<int> &nums2, vector<vector<int>> &queries) {
        int n = nums1.size();
        vector<pair<int, int>> nums(n);
        for (int i = 0; i < n; i++) {
            nums[i] = {nums1[i], nums2[i]};
        }
        sort(nums.begin(), nums.end());

        vector<pair<vector<int>, vector<int>>> segmentTree(4 * n);
        build(0, 0, n - 1, nums, segmentTree);

        vector<int> ans;
        for (auto &qr : queries) {
            int xi = qr[0], yi = qr[1];
            auto it = lower_bound(nums.begin(), nums.end(), make_pair(xi, INT_MIN));
            int j = it - nums.begin();
            if (j == n) {
                ans.push_back(-1);
                continue;
            }
            int q = query(j, n - 1, yi, 0, 0, n - 1, segmentTree);
            ans.push_back(q);
        }    
        return ans;
    }
};

```
['Binary Search', 'Segment Tree', 'Merge Sort', 'C++']