Sorting + Merge Sort Tree + Suffix array
Intuition\nMerge Sort Tree\n\n# Approach\nin Code\n\n# Complexity\n- Time complexity:\nO(nlogn)\n\n- Space complexity:\nO(nlogn)\n\n# Code\n\n#include <vector>\
# Intuition\nMerge Sort Tree\n\n# Approach\nin Code\n\n# Complexity\n- Time complexity:\n`O(nlogn)`\n\n- Space complexity:\n`O(nlogn)`\n\n# Code\n```\n#include <vector>\n#include <algorithm>\n\nusing namespace std;\n\nclass Solution {\npublic:\n    vector<int> maximumSumQueries(vector<int>& nums1, vector<int>& nums2, vector<vector<int>>& queries) {\n        int n = nums1.size();\n        vector<pair<int,int>> a(n);\n        for(int i = 0; i < nums1.size(); i++){\n            a[i] = {nums1[i], nums2[i]};\n        }\n        sort(a.begin(), a.end());\n        vector<vector<pair<int,int>>> tree(2*n+2);\n        vector<vector<int>> suff(2*n+2);\n        for(int i = 0; i < n; i++){\n            tree[i+n].push_back({a[i].second, a[i].first + a[i].second});\n            suff[i+n].push_back(a[i].first + a[i].second);\n        }\n        auto mergee = [&](vector<pair<int,int>>& tr, vector<pair<int,int>>& t1, vector<pair<int,int>>& t2) {\n            int p1 = 0, p2 = 0;\n            while(p1 < t1.size() && p2 < t2.size()) {\n                if(t1[p1].first < t2[p2].first) tr.push_back(t1[p1++]);\n                else tr.push_back(t2[p2++]);\n            }\n            while(p1 < t1.size()) tr.push_back(t1[p1++]);\n            while(p2 < t2.size()) tr.push_back(t2[p2++]);\n        };\n        for(int i = n-1; i >= 1; i--){\n            mergee(tree[i], tree[i<<1], tree[i<<1|1]);\n            suff[i].assign(tree[i].size(), 0);\n            suff[i][tree[i].size()-1] = tree[i].back().second;\n            for(int j = tree[i].size()-2; j >= 0; j--){\n                suff[i][j] = max(suff[i][j+1], tree[i][j].second);\n            }\n        }\n        auto query = [&](int l, int r, int y){\n            l += n;\n            r += n;\n            int mx = -1;\n            while(l < r){\n                if(l & 1){\n                    auto it = lower_bound(tree[l].begin(), tree[l].end(), make_pair(y, -1));\n                    if(it != tree[l].end()) {\n                        int idx = it - tree[l].begin();\n                        mx = max(mx, suff[l][idx]);\n                    }\n                    l++;\n                }\n                if(r & 1){\n                    --r;\n                    auto it = lower_bound(tree[r].begin(), tree[r].end(), make_pair(y, -1));\n                    if(it != tree[r].end()) {\n                        int idx = it - tree[r].begin();\n                        mx = max(mx, suff[r][idx]);\n                    }\n                }\n                l >>= 1;\n                r >>= 1;\n            }\n            return mx;\n        };\n        vector<int> ans;\n        for(auto& c : queries){\n            int x = c[0];\n            int y = c[1];\n            auto it = lower_bound(a.begin(), a.end(), make_pair(x, -1)) - a.begin();\n            if(it == n){\n                ans.push_back(-1);\n                continue;\n            }\n            int mx = query(it, n, y);\n            ans.push_back(mx);\n        }\n        return ans;\n    }\n};\n\n```
['Suffix Array', 'Merge Sort', 'C++']