TypeScript | Treap (aka Cartesian Tree) | 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 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    private constructor(public X: number, public Y: number) {\n    }\n\n    // Adds a point to the treap and returns the new root\n    static add(x: number, y: number, treap?: Treap): Treap {\n\n        const newNode = new Treap(x, y);\n\n        if (!treap) {\n            return newNode; \n        }\n\n        const splitResult = treap.split(x);\n\n        const moreOrEqual = Treap.merge(newNode, splitResult.right);\n\n        return Treap.merge(splitResult.left, moreOrEqual);\n    }\n\n    // Returns a new treap containing all points with X >= minX\n    moreOrEqualThanX(minX: number): Treap {\n\n        return this.split(minX).right;\n    }\n\n    // Returns maximum across all points with Y >= minY\n    maxValueAcrossMoreOrEqualThanY(minY: number): number {\n\n        let 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        let node: Treap = this;\n        while (node?.Y >= minY) {\n\n            if (result < node.Value) {\n                result = node.Value;\n            }\n\n            node = node._right;\n        }\n\n        return result;\n    }\n\n    private _left: Treap; \n    private _right: Treap;\n\n    private get Value(): number { return this.X + this.Y; }\n\n    // Splits a treap into two halves by X coordinate\n    private split(x: number) : {left?: Treap, right?: Treap} {\n\n        const result: {left?: Treap, right?: Treap} = {};\n\n        if (this.X >= x) {\n\n            result.right = this;\n\n            if (this._left) {\n\n                const splitResult = this._left.split(x);\n\n                this._left = splitResult.right;\n                result.left = splitResult.left;\n            }\n\n        } else {\n\n            result.left = this;\n\n            if (this._right) {\n\n                const splitResult = this._right.split(x);\n\n                this._right = splitResult.left;\n                result.right = splitResult.right;\n            }\n        }\n\n        return result;\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 merge(left: Treap, right: Treap) : Treap {\n\n        if (!left) {\n            return right;\n        }\n\n        if (!right) {\n            return left;\n        }\n\n        if (left.Y > right.Y) {\n\n            left._right = Treap.merge(left._right, right);\n\n            return left;\n\n        } else {\n\n            right._left = Treap.merge(left, right._left);\n\n            return right;\n        }\n    }\n}\n\nfunction maximumSumQueries(nums1: number[], nums2: number[], queries: number[][]): number[] {\n\n    // Initializing Treap\n    let treap: Treap;\n    for (let i = 0; i < nums1.length; i++) {\n        treap = Treap.add(nums1[i], nums2[i], treap);\n    }\n\n    // Also need to convert queries into a two-dimentional map\n    const queryResults: { [x: number] : { [y: number] : number } } = {};\n    for (const query of queries) {\n\n        queryResults[query[0]] ??= {};\n        queryResults[query[0]][query[1]] = -1;\n    }\n\n    // Properties in a JavaScript object are natively sorted in ascending order, if their names are numbers.\n    // So we just need to iterate through queryResults\n    for (const x in queryResults) {\n\n        // Removing all nodes with X < x\n        treap = treap.moreOrEqualThanX(x as any);\n        if (!treap) {\n            break;\n        }\n\n        for (const y in queryResults[x]) {\n\n            // Now obtaining results for given x and y\n            queryResults[x][y] = treap.maxValueAcrossMoreOrEqualThanY(y as any);\n        }\n    }\n\n    // Formatting output\n    return queries.map(query => queryResults[query[0]][query[1]]);\n};\n\n```
['TypeScript']