C++ | Treap (aka Cartesian Tree) | 332ms | Detailed Explanation
Approach\n\nLet\'s use these input arrays as an example:\n\n[7,3,4,8,9,6]\n[5,4,2,2,4,8]\n\n\nLet\'s think of them as of coordinates in a 2D space and plot them
# Approach\n\nLet\'s use these input arrays as an example:\n```\n[7,3,4,8,9,6]\n[5,4,2,2,4,8]\n```\n\nLet\'s think of them as of coordinates in a 2D space and plot them as points on a surface:\n\n![image.png](https://assets.leetcode.com/users/images/af27f9a4-9369-4ecc-a133-3fdeeed25a10_1702144545.989097.png)\n\nFirst two digits in a point are coordinates and the third one is the *sum* of them, which we will further on refer to as the *point\'s value* and use later as a result.\n\nNow let\'s use `[5,2]` as a query. It is now plain to see that what a query actually does is just limiting the area of interest, aka filtering out the points that have coordinates below the query values:\n \n![image.png](https://assets.leetcode.com/users/images/e1f5f387-6bd0-4723-8a13-14211ff2ff71_1702148636.2271185.png)\n\nSo we just need to find a maximum value across all the remaining points. For this sample query it will be `14`.\n\nLet\'s take another illustrative query example - `[7,5]`. Then the plot will look like this:\n\n![image.png](https://assets.leetcode.com/users/images/5ce0e228-aea2-4f69-82a2-dacc8e1d928c_1702146222.2673829.png)\n\nand the answer will be `12`.\n\nNow we just need a data structure that efficiently produces a maximum value across a filtered subset of 2D points.\nWhen looking at those plots a [Treap](https://en.wikipedia.org/wiki/Treap) (also known as a Cartesian Tree) comes into mind immediately. \n\nBy its definition, it arranges points as a Binary Search Tree by their X coordinate, and also as a Heap by their Y coordinate. So for this example the tree will look like this:\n\n![image.png](https://assets.leetcode.com/users/images/7a540c67-5a73-4c78-83cb-fb37f18218ae_1702146884.0119817.png)\n\nNote that there\'s always *only one* way of arranging points as a Treap - and that\'s the beauty of it. Also note that we\'re using our Y coordinates for building that heap, *not* the point\'s values.\n\nAnother useful feature of a Treap for us will be that it can be efficiently (O(log(n))) split into two halves by a given X coordinate - everything *less than* a given X will go into a left half and everything *more or equal* than X will go into a right one. That *Split* operation is destructive (the original treap will be lost), but that\'s OK for us - we can just process the queries *in ascending order* (by their first number, aka by their X coordinate) and *gradually filter out* the unneeded points by X.\n\nOnce filtered by X, next we would need to filter the remaining points by Y. Since by Y it is a heap, we can just traverse the tree breadth-first and stop, when Y goes below a given query value. And while doing that we can simultaneously calculate the maximum of those point\'s values. Normally this would require traversing the whole tree (because remember, it\'s our Y coordinates that produce the heap, not point\'s values). But now we remember that a point\'s value is just a sum of its coordinates, therefore *its maximum has no chance to appear to the left of a tree\'s root* (try to prove this geometrically yourself). So we can safely traverse *only the right part* of our treap:\n\n![image.png](https://assets.leetcode.com/users/images/72080f89-0fce-4932-b304-1e4634f69349_1702148970.04745.png)\n\nand that greatly saves time. \n\nAlso, since our point\'s value is a sum of that point\'s coordinates, we do not actually need to store that value, and instead we can always calculate it on-the-fly. And that is a great space optimization.\n\n\n# Code\n```\n// Implements a Treap (Cartesian Tree)\nstruct Treap \n{\npublic:\n\n    int X;\n    int Y;\n\n    // Adds a point to the treap and returns the new root\n    static Treap* Add(int x, int y, Treap* treap)\n    {\n        Treap* newNode = new Treap(x, y);\n        if (treap == NULL)\n        {\n            return newNode;\n        }\n\n        Treap* less, *moreOrEqual;\n\n        treap->Split(x, less, moreOrEqual);\n\n        moreOrEqual = Merge(newNode, moreOrEqual);\n        \n        return Merge(less, moreOrEqual);\n    }\n\n    // Returns a new treap containing all points with X >= minX\n    Treap* MoreOrEqualThanX(int minX)\n    {\n        Treap* less, *moreOrEqual;\n\n        Split(minX, less, moreOrEqual);\n\n        return moreOrEqual;\n    }\n\n    // Returns maximum across all points with Y >= minY\n    int MaxValueAcrossMoreOrEqualThanY(int minY)\n    {\n        int result = -1;\n\n        // In our particular case points to the left can never have \n        // a Value more than points to the right (because Value is a sum of X and Y).\n        // Therefore we just need to traverse the right branch only.\n        Treap* node = this;\n        while (node != NULL && node->Y >= minY)\n        {\n            if (result < node->Value())\n            {\n                result = node->Value();\n            }\n\n            node = node->_right;\n        }\n\n        return result;\n    }\n\nprivate:\n\n    Treap* _left = NULL;\n    Treap* _right = NULL;\n\n    Treap(int x, int y)\n    {\n        X = x;\n        Y = y;\n    }\n\n    int Value()\n    {\n        return X + Y;\n    }\n\n    // Splits a treap into two halves by X coordinate\n    void Split(int x, Treap*& left, Treap*& right)\n    {\n        if (X >= x)\n        {\n            right = this;\n            left = NULL;\n\n            if (_left != NULL)\n            {\n                _left->Split(x, left, _left);               \n            }\n        }\n        else\n        {\n            left = this;\n            right = NULL;\n\n            if (_right != NULL) \n            {\n                _right->Split(x, _right, right);\n            }\n        }\n    }\n\n    // Merges two treaps and returns the new root.\n    // All points in left are supposed to have their X coordinate\n    // _less_ than all points in right.\n    static Treap* Merge(Treap* left, Treap* right)\n    {\n        if (left == NULL)\n        {\n            return right;\n        }\n\n        if (right == NULL)\n        {\n            return left;\n        }\n\n        if (left->Y > right->Y)\n        {\n            left->_right = Merge(left->_right, right);\n\n            return left;\n        }\n        else\n        {\n            right->_left = Merge(left, right->_left);\n\n            return right;\n        }\n    }\n};\n\nclass Solution \n{\npublic:\n    vector<int> maximumSumQueries(vector<int>& nums1, vector<int>& nums2, vector<vector<int>>& queries) {\n        \n        // Initializing Treap\n        Treap* treap = NULL;\n        for (int i = 0; i < nums1.size(); i++)\n        {\n            treap = Treap::Add(nums1[i], nums2[i], treap);\n        }\n\n        // Need to convert queries into a map sorted by X. Also need to keep track of the query\'s original index, so that we can access it later.\n        multimap<int, int> queryMap;\n        for (int i = 0; i < queries.size(); i++)\n        {\n            queryMap.insert(  make_pair( queries[i][0], i )  );\n        }\n\n        vector<int> result(queries.size());\n\n        // Now going from minimum X to maximum X\n        for (auto it = queryMap.begin(); it != queryMap.end(); it++)\n        {\n            // Removing all nodes with X < current x\n            treap = treap == NULL ? NULL : treap->MoreOrEqualThanX( it->first );\n\n            // Now obtaining a result for given x and y\n            result[it->second] = treap == NULL ? -1 : treap->MaxValueAcrossMoreOrEqualThanY( queries[it->second][1] );\n        }\n\n        return result;\n    }\n};\n```
['C++']