Video Explanation (2 Approaches - Merge Sort Tree & Usual Segment Trees)
Explanation\n\nclick here for the video\n\n# Code\n\n#define pii pair<int, int>\n#define F first\n#define S second\n\nstruct SegmentTree {\npublic:\n    Segment
# Explanation\n\n[click here for the video](https://youtu.be/XU7Wu70XpBw)\n\n# Code\n```\n#define pii pair<int, int>\n#define F first\n#define S second\n\nstruct SegmentTree {\npublic:\n    SegmentTree (int _n) : n(_n) {\n        tree.resize(4*n, -1);\n    }\n    \n    void update (int ind, int val) {\n        update (ind, val, 0, n-1, 0);\n    }\n    \n    int query (int x, int y) {\n        return query (x, y, 0, n-1, 0);\n    }\n    \nprivate:\n    vector<int> tree;\n    int n;\n    \n    void update (int ind, int val, int l, int r, int i) {\n        if (l == r) {\n            tree[i] = val;\n            return;\n        }\n        \n        int m = (l+r) >> 1;\n        if (m >= ind) update (ind, val, l, m, i*2+1);\n        else update (ind, val, m+1, r, i*2+2);\n        \n        tree[i] = max (tree[i*2+1], tree[i*2+2]);\n    }\n    \n    int query (int x, int y, int l, int r, int i) {\n        if (r < x || l > y) return -1;\n        if (l >= x && r <= y) return tree[i];\n        \n        int m = (l+r) >> 1;\n        return max (\n            query (x, y, l, m, i*2+1),\n            query (x, y, m+1, r, i*2+2)\n        );\n    }\n};\n\nstruct Node {\n    int val, ind;\n    int sum;\n    \n    Node (int _ind, int _val, int _sum) : ind(_ind), val(_val), sum(_sum) {}\n    \n    bool operator < (const Node& rhs) const {\n        return val > rhs.val;\n    }\n};\n\nstruct Query {\n    int num1, num2, ind;\n    \n    Query (int _num1, int _num2, int _ind) : num1(_num1), num2(_num2), ind(_ind) {}\n    \n    bool operator < (const Query& rhs) {\n        return num2 > rhs.num2;\n    }\n};\n\nclass Solution {\npublic:\n    vector<int> maximumSumQueries(vector<int>& nums1, vector<int>& nums2, vector<vector<int>>& queries) {\n        int n = nums1.size();\n        SegmentTree tree(n);\n        \n        vector<pii> num1_and_ind;\n        vector<Node> num2_ind_and_sum;        \n    \n        for (int j = 0; j < n; j ++) num1_and_ind.push_back({nums1[j], j});\n        sort (num1_and_ind.begin(), num1_and_ind.end());\n        \n        for (int j = 0; j < n; j ++) {\n            int ind = num1_and_ind[j].S;\n            num2_ind_and_sum.push_back(Node(j, nums2[ind], nums1[ind]+nums2[ind]));\n        }\n        sort (num2_ind_and_sum.begin(), num2_ind_and_sum.end());\n        \n        vector<Query> query;\n        for (int j = 0; j < queries.size(); j ++) {\n            query.push_back(Query(queries[j][0], queries[j][1], j));\n        }\n        sort (query.begin(), query.end());\n        \n        vector<int> result(queries.size());\n        int inactive_ind = 0;\n\n        for (auto q: query) {\n            while (inactive_ind < n && num2_ind_and_sum[inactive_ind].val >= q.num2) {\n                const Node& node = num2_ind_and_sum[inactive_ind];\n                tree.update (node.ind, node.sum);\n                inactive_ind ++;\n            }\n            \n            int l = lower_bound(num1_and_ind.begin(), num1_and_ind.end(), make_pair(q.num1, -1)) - num1_and_ind.begin();\n            int r = n-1;\n            \n            result[q.ind] = (l <= r)? tree.query(l, r) : -1;\n        }\n        return result;\n    }\n};\n```
['C++']