Merge Sort Tree | Segment Trees
Code
# Code
```cpp []
#define ll long long
class MergeSortTree {
private:
    struct Node {
        vector<ll> sorted;
        vector<ll> suffix_max;
    };
    vector<Node> tree;
    ll n;

    void build(vector<ll>& arr1, vector<ll>& arr2, ll start, ll end, ll node) {
        if (start == end) {
            tree[node].sorted.push_back(arr1[start]);
            tree[node].suffix_max.push_back(arr2[start]);
            return;
        }
        ll mid = start + (end - start) / 2; 
        build(arr1, arr2, start, mid, 2 * node + 1);
        build(arr1, arr2, mid + 1, end, 2 * node + 2);

        vector<ll>& merged_values = tree[node].sorted;
        vector<ll>& merged_suffix = tree[node].suffix_max;
        
        ll i = 0, j = 0;
        while (i < tree[2 * node + 1].sorted.size() || j < tree[2 * node + 2].sorted.size()) {
            if (j == tree[2 * node + 2].sorted.size() || 
                (i < tree[2 * node + 1].sorted.size() && 
                 tree[2 * node + 1].sorted[i] <= tree[2 * node + 2].sorted[j])) {
                merged_values.push_back(tree[2 * node + 1].sorted[i]);
                merged_suffix.push_back(tree[2 * node + 1].suffix_max[i]);
                i++;
            } else {
                merged_values.push_back(tree[2 * node + 2].sorted[j]);
                merged_suffix.push_back(tree[2 * node + 2].suffix_max[j]);
                j++;
            }
        }
        
        for (ll i = merged_suffix.size() - 2; i >= 0; i--) {
            merged_suffix[i] = max(merged_suffix[i], merged_suffix[i + 1]);
        }
    }

    ll query(ll l, ll r, ll k, ll start, ll end, ll node) {
        if (l > end || r < start) return LLONG_MIN;
        if (l <= start && r >= end) {
            auto it = lower_bound(tree[node].sorted.begin(), tree[node].sorted.end(), k);
            if (it == tree[node].sorted.end()) return -1;
            ll idx = it - tree[node].sorted.begin();
            return tree[node].suffix_max[idx];
        }
        ll mid = start + (end - start) / 2;  
        return max(query(l, r, k, start, mid, 2 * node + 1),
                   query(l, r, k, mid + 1, end, 2 * node + 2));
    }

    void update(ll idx, ll value1, ll value2, ll start, ll end, ll node) {
        if (start == end) {
            tree[node].sorted[0] = value1;  
            tree[node].suffix_max[0] = value2;
            return;
        }
        ll mid = start + (end - start) / 2;  
        if (idx <= mid) {
            update(idx, value1, value2, start, mid, 2 * node + 1);
        } else {
            update(idx, value1, value2, mid + 1, end, 2 * node + 2);
        }

        vector<ll>& merged_values = tree[node].sorted;
        vector<ll>& merged_suffix = tree[node].suffix_max;
        merged_values.clear();  
        merged_suffix.clear();
        
        ll i = 0, j = 0;
        while (i < tree[2 * node + 1].sorted.size() || j < tree[2 * node + 2].sorted.size()) {
            if (j == tree[2 * node + 2].sorted.size() || 
                (i < tree[2 * node + 1].sorted.size() && 
                 tree[2 * node + 1].sorted[i] <= tree[2 * node + 2].sorted[j])) {
                merged_values.push_back(tree[2 * node + 1].sorted[i]);
                merged_suffix.push_back(tree[2 * node + 1].suffix_max[i]);
                i++;
            } else {
                merged_values.push_back(tree[2 * node + 2].sorted[j]);
                merged_suffix.push_back(tree[2 * node + 2].suffix_max[j]);
                j++;
            }
        }
        
        for (ll i = merged_suffix.size() - 2; i >= 0; i--) {
            merged_suffix[i] = max(merged_suffix[i], merged_suffix[i + 1]);
        }
    }

public:
    MergeSortTree(vector<ll>& arr1, vector<ll>& arr2) {
        n = arr1.size();
        tree.resize(4 * n);  
        build(arr1, arr2, 0, n - 1, 0);
    }

    ll query(ll l, ll r, ll k) {
        return query(l, r, k, 0, n - 1, 0);
    }

    void update(ll idx, ll value1, ll value2) {
        update(idx, value1, value2, 0, n - 1, 0);
    }
};

class Solution {
public:
    vector<int> maximumSumQueries(vector<int>& nums1, vector<int>& nums2, vector<vector<int>>& queries) {
        ll n = nums1.size();
        vector<pair<ll, ll>> v(n); 
        for(ll i = 0; i < n; i++){
            v[i] = {nums1[i], nums2[i]};
        }
        sort(v.begin(), v.end());
        
        vector<ll> a(n), b(n), p(n); 
        for(ll i = 0; i < n; i++){
            a[i] = v[i].first;
            b[i] = v[i].second;
            p[i] = b[i] + a[i];
        }
        
        MergeSortTree mgt(b, p);
        vector<int> yy(queries.size());  
        
        for(ll i = 0; i < queries.size(); i++){
            ll x = queries[i][0];
            ll y = queries[i][1];
            ll idx = lower_bound(a.begin(), a.end(), x) - a.begin();
            ll ans = (idx == n ? -1 : mgt.query(idx, n - 1, y));
            yy[i] = (ans == LLONG_MIN ? -1 : (int)ans);
        }
        return yy;
    }
};
```
['C++']