JS Solution - Monotonic stack + Segment tree
LOL I was about to add binary search which could make the code even longer, then I realized Segment tree was more than enough.\n\n# Complexity\n- Time complexit
LOL I was about to add binary search which could make the code even longer, then I realized Segment tree was more than enough.\n\n# Complexity\n- Time complexity: $$O(nlog(n))$$\n- Space complexity: $$O(n)$$\n\n# Code\n```js\n//#region Optimized Stack\n/**\n * @template TItem\n */\nclass OptStack {\n  /**\n   * @type {TItem[]}\n   * @private\n   */\n  _array;\n  /**\n   * @type {number}\n   * @private\n   */\n  _size;\n\n  constructor(initialSize = 0) {\n    this._array = Array(initialSize).fill();\n    this.clear();\n  }\n\n  get size() {\n    return this._size;\n  }\n\n  clear() {\n    this._size = 0;\n  }\n\n  /**\n   * @param  {...TItem} items\n   */\n  push(...items) {\n    for (let i = 0; i < items.length; i++) {\n      if (this._array.length === this._size) this._array.push(items[i]);\n      else this._array[this._size] = items[i];\n      this._size++;\n    }\n  }\n\n  pop() {\n    if (this._size) return this._array[--this._size];\n    return undefined;\n  }\n\n  /**\n   * @param {number} i offset from last element. Default to 0, which is the last element itself\n   * @returns\n   */\n  getLast(i = 0) {\n    if (this._size > i) return this._array[this._size - i - 1];\n    return undefined;\n  }\n\n  /**\n   * @param {number} i offset from first element. Default to 0, which is the first element itself\n   * @returns\n   */\n  getFirst(i = 0) {\n    if (i < this._size) return this._array[i];\n    return undefined;\n  }\n}\n//#endregion\n\nclass IntervalTree {\n  /**\n   * @param {OptStack<number>} st\n   * @param {number[]} nums1\n   * @param {number[]} nums2\n   */\n  constructor(st, nums1, nums2) {\n    let size = st.size;\n    this.vals = new Uint32Array(size * 4);\n    this.st = st;\n    this.nums1 = nums1;\n    this.nums2 = nums2;\n\n    const build = (index, l, r) => {\n\n      if (l === r) {\n        this.vals[index] = nums1[st.getFirst(l)] + nums2[st.getFirst(l)];\n      } else {\n        const mid = (l + r) >> 1;\n        this.vals[index] = Math.max(\n          build(2 * index + 1, l, mid),\n          build(2 * index + 2, mid + 1, r)\n        );\n      }\n\n      return this.vals[index];\n    };\n    build(0, 0, size - 1);\n  }\n\n  query(x, y, rootIndex, l, r) {\n    let nl1 = this.nums1[this.st.getFirst(l)];\n    let nl2 = this.nums2[this.st.getFirst(l)];\n    let nr1 = this.nums1[this.st.getFirst(r)];\n    let nr2 = this.nums2[this.st.getFirst(r)];\n\n    if (nr1 < x || nl2 < y) return -1;\n    if (nl1 >= x && nr2 >= y) return this.vals[rootIndex];\n\n    const m = (l + r) >> 1;\n    return Math.max(\n      this.query(x, y, 2 * rootIndex + 1, l, m),\n      this.query(x, y, 2 * rootIndex + 2, m + 1, r)\n    );\n  }\n}\n\nlet st = new OptStack(0);\n\n/**\n * @param {number[]} nums1\n * @param {number[]} nums2\n * @param {number[][]} queries\n * @return {number[]}\n */\nvar maximumSumQueries = function (nums1, nums2, queries) {\n  let n = nums1.length;\n  let indices = new Uint32Array(n);\n  for (let i = 0; i < n; i++) indices[i] = i;\n\n  indices.sort((a, b) => nums1[a] - nums1[b]);\n  st.clear();\n  st.push(indices[0]);\n\n  for (let i = 1; i < n; i++) {\n    while (st.size && nums2[indices[i]] >= nums2[st.getLast()]) st.pop();\n    st.push(indices[i]);\n  }\n\n  n = st.size - 1;\n  let it = new IntervalTree(st, nums1, nums2);\n  let res = Array(queries.length).fill();\n  for (let i = 0; i < queries.length; i++)\n    res[i] = it.query(queries[i][0], queries[i][1], 0, 0, n);\n\n  return res;\n};\n```
['Segment Tree', 'Monotonic Stack', 'JavaScript']