[Javascript] Segment Tree
Solution: Segment Tree\n\n1. Collect tuples of each (nums1[j], nums2[j]) and sort by nums1[j] in desc order.\n2. Sort the queries in desc order by x, then y.\n3
**Solution: Segment Tree**\n\n1. Collect tuples of each `(nums1[j], nums2[j])` and sort by `nums1[j]` in desc order.\n2. Sort the queries in desc order by `x`, then `y`.\n3. Go through each query and use a segment tree to keep track of maximum (`nums1[j] + nums2[j]`) for each range. `index[nums2[j]]` is used for the range.\n  a. Keep a pointer in nums and move it right while `nums1[j] >= the current x`. Update the values in the segment tree as we move the pointer.\n  b. The answer of the query is the maximum (`nums1[j] + nums2[j]`) in range `(y, end of segment tree)`\n\nNote: Since `nums2[i] and y <= 10^9`, we need to convert these to the minimal form and assign a count starting from `0`.\n\n`n = length of nums1`, `m = number of queries`\nTime Complexity: `O(n log(n) + m log(m + n))`  \nSpace Complexity: `O(m + n)`\n```\nvar maximumSumQueries = function(nums1, nums2, queries) {\n  let nums = [], n = nums1.length, indexMap = {}; \n  for (let i = 0; i < n; i++) {\n    nums.push([nums1[i], nums2[i]]);\n    indexMap[nums2[i]] = 1;\n  }\n  nums.sort((a, b) => a[0] === b[0] ? b[1] - a[1] : b[0] - a[0]);\n  for (let [_x, y] of queries) {\n    indexMap[y] = 1;\n  }\n  let index = 0;\n  for (let value in indexMap) {\n    indexMap[value] = index++; // assign a minimized index to each value\n  }\n  queries = queries.map(([x, y], i) => [x, y, i]).sort((a, b) => a[0] === b[0] ? b[1] - a[1] : b[0] - a[0]);\n\n  let m = queries.length, ans = Array(m);\n  let segTree = new SegmentTree(index), numsIndex = 0;\n  for (let [x, y, queryIndex] of queries) {\n    while (numsIndex < n && nums[numsIndex][0] >= x) {\n      segTree.update(indexMap[nums[numsIndex][1]], nums[numsIndex][0] + nums[numsIndex][1]);\n      numsIndex++;\n    }\n    let max = segTree.maxRange(indexMap[y], index - 1);\n    ans[queryIndex] = max === 0 ? -1 : max;\n  }\n  return ans;\n};\n\nclass SegmentTree {\n  constructor(n) {\n    this.size = n;\n    this.segTree = Array(n * 2).fill(0);\n  }\n  update(index, val) {\n    let n = this.size, idx = index + n;\n    this.segTree[idx] = Math.max(this.segTree[idx], val);\n    idx = Math.floor(idx / 2);\n\n    while (idx > 0) {\n      this.segTree[idx] = Math.max(this.segTree[idx * 2], this.segTree[idx * 2 + 1]);\n      idx = Math.floor(idx / 2);\n    }\n  }\n  maxRange(left, right) {\n    let n = this.size, max = 0;\n    let left_idx = left + n, right_idx = right + n;\n    while (left_idx <= right_idx) {\n      if (left_idx % 2 === 1) max = Math.max(max, this.segTree[left_idx++]);\n      if (right_idx % 2 === 0) max = Math.max(max, this.segTree[right_idx--]);\n      left_idx = Math.floor(left_idx / 2);\n      right_idx = Math.floor(right_idx / 2);\n    }\n    return max;\n  }\n}\n```
['JavaScript']