C# | Treap (aka Cartesian Tree) | Detailed Explanation
\n# 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 
\n# 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# Code\n```\n// Implements a Treap (Cartesian Tree)\nclass Treap\n{\n    public int X { get; private set; }\n    public int Y { get; private set; }\n\n    private Treap(int x, int y)\n    {\n        this.X = x;\n        this.Y = y;\n    }\n\n    // Adds a point to the treap and returns the new root\n    public static Treap? Add(int x, int y, Treap? treap)\n    {\n        var newNode = new Treap(x, y);\n        if (treap == null) \n        {\n            return newNode;\n        }\n\n        treap.Split(x, out var less, out var 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    public Treap? MoreOrEqualThanX(int minX)\n    {\n        this.Split(minX, out var less, out var moreOrEqual);\n\n        return moreOrEqual;\n    }\n\n    // Returns maximum across all points with Y >= minY\n    public 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        var 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\n    private Treap? _left;\n    private Treap? _right;\n\n    private int Value => this.X + this.Y;\n\n    // Splits a treap into two halves by X coordinate\n    private void Split(int x, out Treap? left, out Treap? right)\n    {\n        if (this.X >= x)\n        {\n            right = this;\n            left = null;\n\n            if (this._left != null)\n            {\n                this._left.Split(x, out left, out this._left);\n            }\n        }\n        else\n        {\n            left = this;\n            right = null;\n\n            if (this._right != null)\n            {\n                this._right.Split(x, out this._right, out 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    private 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\npublic class Solution \n{\n    public int[] MaximumSumQueries(int[] nums1, int[] nums2, int[][] queries) \n    {\n        var result = new int[queries.Length];\n\n        // Initializing Treap\n        Treap treap = null;\n        for (int i = 0; i < nums1.Length; i++)\n        {\n            treap = Treap.Add(nums1[i], nums2[i], treap);\n        }\n\n        // Need to convert queries into a list sorted by X. Also storing each query\'s original index, so that we can reconstruct the result\n        int j = 0;\n        var queryMap = queries\n            .Select(query => new { x = query[0], y = query[1], index = j++ })\n            .OrderBy(query => query.x);\n\n        foreach (var query in queryMap)\n        {\n            // Removing all nodes with X < xy.Item1\n            treap = treap?.MoreOrEqualThanX(query.x);\n\n            // Now obtaining a result for given X and Y\n            result[query.index] = treap == null ? -1 : treap.MaxValueAcrossMoreOrEqualThanY(query.y);\n        }\n\n        return result;\n    }\n}\n```
['C#']