Range Sum of Sorted Subarray Sums

Description

Given the array nums consisting of n positive integers. You computed the sum of all non-empty continous subarrays from the array and then sort them in non-decreasing order, creating a new array of n * (n + 1) / 2 numbers.

Return the sum of the numbers from index left to index right (indexed from 1), inclusive, in the new array. Since the answer can be a huge number return it modulo 10^9 + 7.

 

Example 1:

Input: nums = [1,2,3,4], n = 4, left = 1, right = 5
Output: 13 
Explanation: All subarray sums are 1, 3, 6, 10, 2, 5, 9, 3, 7, 4. After sorting them in non-decreasing order we have the new array [1, 2, 3, 3, 4, 5, 6, 7, 9, 10]. The sum of the numbers from index le = 1 to ri = 5 is 1 + 2 + 3 + 3 + 4 = 13. 

Example 2:

Input: nums = [1,2,3,4], n = 4, left = 3, right = 4
Output: 6
Explanation: The given array is the same as example 1. We have the new array [1, 2, 3, 3, 4, 5, 6, 7, 9, 10]. The sum of the numbers from index le = 3 to ri = 4 is 3 + 3 = 6.

Example 3:

Input: nums = [1,2,3,4], n = 4, left = 1, right = 10
Output: 50

 

Constraints:

• 1 <= nums.length <= 10^3
• nums.length == n
• 1 <= nums[i] <= 100
• 1 <= left <= right <= n * (n + 1) / 2

Solution(javascript)

// /** 可以用 Heap ？可以！
//  * 1. 暴力解法
//  * @param {number[]} nums
//  * @param {number} n
//  * @param {number} left
//  * @param {number} right
//  * @return {number}
//  */
// const rangeSum = function (nums, n, left, right) {
//   // nums.sort((a, b) => a - b)
//   const arr = []
//   for (let i = 0; i < nums.length; i++) {
//     let current = nums[i]
//     arr.push(current)
//     for (let j = i + 1; j < nums.length; j++) {
//       current += nums[j]
//       arr.push(current)
//     }
//   }
//   arr.sort((a, b) => a - b)
//   // console.log(arr)
//   return arr.slice(left - 1, right).reduce((acc, num) => acc + num, 0)
// }

class Heap {
  constructor(list, compare = (a, b) => a - b) {
    this.left = index => 2 * index + 1
    this.right = index => 2 * index + 2
    this.parent = index => Math.floor((index - 1) / 2)
    this.heapify = (index = 0) => {
      const { list } = this
      const leftIndex = this.left(index)
      const rightIndex = this.right(index)
      let maxIndex = index
      if (list[leftIndex] !== undefined
        && this.compare(list[maxIndex], list[leftIndex]) > 0) {
        maxIndex = leftIndex
      }
      if (list[rightIndex] !== undefined
        && this.compare(list[maxIndex], list[rightIndex]) > 0) {
        maxIndex = rightIndex
      }
      if (index !== maxIndex) {
        const temp = list[index]
        list[index] = list[maxIndex]
        list[maxIndex] = temp
        this.heapify(maxIndex)
      }
    }
    this.buildHeap = () => {
      for (let i = Math.floor(this.list.length / 2); i >= 0; i--) {
        this.heapify(i)
      }
      return this.list
    }
    this.extract = () => {
      const temp = this.list[0]
      this.list[0] = this.list[this.list.length - 1]
      this.list[this.list.length - 1] = temp
      const result = this.list.pop()
      this.heapify(0)
      return result
    }
    this.insert = (item) => {
      const { list } = this
      list.push(item)
      let index = list.length - 1
      let parentIndex = this.parent(index)
      while (list[parentIndex] !== undefined && this.compare(list[parentIndex], list[index]) > 0) {
        const temp = list[index]
        list[index] = list[parentIndex]
        list[parentIndex] = temp
        index = parentIndex
        parentIndex = this.parent(index)
      }
    }
    this.list = list
    this.compare = compare
    this.buildHeap()
  }
}


/**
 * 1. Heap
 * @param {number[]} nums
 * @param {number} n
 * @param {number} left
 * @param {number} right
 * @return {number}
 */
const rangeSum = function (nums, n, left, right) {
  // nums.sort((a, b) => a - b)
  const heap = new Heap(nums.map((x, index) => [x, index]), (a, b) => a[0] - b[0])
  let res = 0
  const base = (10 ** 9) + 7
  for (let i = 1; i <= right; i++) {
    const [num, index] = heap.extract()
    if (i >= left) {
      res = ((res % base) + (num % base)) % base
    }
    if (nums[index + 1] !== undefined) {
      heap.insert([num + nums[index + 1], index + 1])
    }
  }
  return res
}