Without segment tree || Easy c++ solution
Complexity\n- Time complexity : O(nlogn + qlogn + qlogq)\n Add your time complexity here, e.g. O(n) \n\n- Space complexity : O(n)\n Add your space complexity he
# Complexity\n- Time complexity : O(nlogn + qlogn + qlogq)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity : O(n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n    void update(map<int,int>& values, int key, int value) {\n        auto t = values.lower_bound(key);\n        if(t != values.end() && t->second >= value) return;\n\n        if(t != values.begin()) {\n            --t;\n            while(t->second <= value) {\n                if(t == values.begin()) {\n                    values.erase(t);\n                    break;\n                }\n                else {\n                    values.erase(t--);\n                }\n            }\n        }\n        values.insert({key, value});\n    }\n    int query(map<int,int>& values, int key) {\n        auto t = values.lower_bound(key);\n        return t == values.end() ? -1 : t->second;\n    }\npublic:\n    vector<int> maximumSumQueries(vector<int>& nums1, vector<int>& nums2, vector<vector<int>>& q) {\n        int ns = nums1.size();\n        vector<pair<int, int>> v(ns);\n        for(int i = 0; i < ns; i++) {\n            v[i] = {nums1[i], nums2[i]};\n        }\n        int qs = q.size();\n        vector<int> ind(qs);\n        for(int i = 0; i < qs; i++) {\n            ind[i] = i;\n        }\n        sort(v.begin(), v.end());\n        sort(ind.begin(), ind.end(), [&](const int x, const int y) {\n            return q[x][0] > q[y][0];\n        });\n        vector<int> res(qs);\n        map<int,int> values;\n        for(int i = 0, j = ns - 1; i < qs; i++) {\n            for(; j >= 0 && v[j].first >= q[ind[i]][0]; j--) {\n                update(values, v[j].second, v[j].first + v[j].second);\n            }\n            res[ind[i]] = query(values, q[ind[i]][1]);\n        }\n        return res;\n    }\n};\n```
['C++']