[B] [C] [D]

You are given an array nums that contains n positive integers. You need to compute the sum of all non-empty continuous subarrays and sort them in ascending order, resulting in a new array containing n * (n + 1) / 2 numbers.

Return all sums (including left and right endpoints) with subscripts **left to right (starting with 1) in the new array. Since the answer may be large, you might want to 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 ascending order, we get a new array [1, 2, 3, 3, 4, 5, 6, 7, 9, 10]. The sum of subscripts from le = 1 to RI = 5 is 1 + 2 + 3 + 3 + 4 = 13.Copy the code

Example 2:

Input: nums = [1,2,3,4], n = 4, left = 3, right = 4 Output: 6 Explanation: Given array is the same as example 1, so the new array is [1,2,3, 3,4, 5, 6, 7, 9, 10]. The sum of subscripts from le = 3 to ri = 4 is 3 + 3 = 6.Copy the code

Example 3:

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

Tip:

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

Violent solution

Their thinking

The brute force solution is also the simplest and most straightforward way to do this, which is to use a double-layer loop to get all the subarrays and values and insert an array of and values. Sort ascending arrays of and values. Get the sum of subarrays and values in the interval, and modulo 10^9 + 7.

Code implementation

Var rangeSum = function(nums, n, left, right) {// Initialize sums and const sums = [] i<n; i++){ let sum = nums[i]; sums.push(sum); for(let j = i+1; j<n; j++){ sum += nums[j]; Sumach. Push (sum)} // Sumach. Sort ((a,b) => sumach. for(let i = left-1; i<right; I ++){res += sums[I]} return res%1000000007};Copy the code

Small top heap + multiple merge

Their thinking

First let’s take a look at the process of finding the sum of all subarrays in a double-layer loop with 1,2,3, and 4 as examples.

The outer loop in our violent solution is actually the first element in each row, and the inner loop is the next element in each row. The violent solution is inefficient because no matter where we want the left and right intervals, we’ll find all the subarrays and, unordered, we’ll sort the subarrays and the arrays in ascending order. Here we use the small top heap + multi-way merge technique, to achieve only need to get the first right element, and ensure that the sum of the subarray is from small to large. The idea is as follows: we treat each row as a path, and initially insert the first value of each path into the small top heap, so that the top of the heap stores the minimum value. Next we loop from 1-right, popping the top of the heap each time, because the logic is multi-way merge and stored in the small top heap, the popping of the top of the heap must be the smallest of the unprocessed elements. If the left-right interval is looping at this time, the result value accumulates the subarray and value of the current element, and deduces the next subarray sum of the path based on the current element, and inserts it into the heap. This ensures that each popup of the top element of the heap is the minimum of the unprocessed element, and that all subarrays and subarrays are retrieved. Finally, when I is greater than right, the sum of the subarray sum in the left-right interval is stored in the result value, which can be returned after modulo 10^9 + 7.

Code implementation

Var rangeSum = function(nums, n, left, right) {const heap = new heap (); i < n; I ++) heap.push({I,j: I,sum:nums[I]}) let res = 0 i <= right; I++) {const min = heap.pop() const min = heap.pop(); If (I >= left) res += min.sum If (min.j<n-1) heap.push({I :min.i, j:min.j + 1, sum:min.sum + nums[min.j + 1]})} return res%1000000007}; Constructor () {// Initialize the array and size this.arr = []; this.size = 0; } // Insert operation push(item) {this.arr.push(item); this.size++; If (this.size>1){let cur = this.size-1, parent = (cur-1)>>1; while(cur>0 && this.arr[parent].sum>this.arr[cur].sum){ [this.arr[parent],this.arr[cur]] = [this.arr[cur],this.arr[parent]] cur = parent,parent = (cur-1)>>1; If (this.arr. Length ===1){this.size--; return this.arr.pop() } const res = this.arr[0]; this.arr[0] = this.arr.pop(); this.size--; // Let cur = 0,childl = 1,childr = 2; while( (childl<this.size && this.arr[childl].sum<this.arr[cur].sum) || (childr<this.size && this.arr[childr].sum<this.arr[cur].sum) ){ if(childr<this.size && this.arr[childr].sum<this.arr[childl].sum){ [this.arr[cur],this.arr[childr]] = [this.arr[childr],this.arr[cur]] cur = childr }else{ [this.arr[cur],this.arr[childl]]  = [this.arr[childl],this.arr[cur]] cur = childl } childl = cur*2+1,childr = cur*2+2; } return res; }}Copy the code

At this point we are done with leetcode-1508- subarray and sorted interval sum

If you have any questions or suggestions, please leave a comment!