Range Sum of Sorted Subarray Sums

export function rangeSum(nums: number[], n: number, left: number, right: number): number {
  const MOD = 1_000_000_007;
  const subarraySum: number[] = [];
  for (let i = 0; i < n; i++) {
    let prefixSum = 0;
    for (let j = i; j < n; j++) {
      prefixSum += nums[j];
      subarraySum.push(prefixSum);
    }
  }
  subarraySum.sort((a, b) => a - b);
  return subarraySum.slice(left - 1, right).reduce((acc, num) => acc + (num % MOD), 0);
}

import { Heap } from '@algorithm/lib';
 
export function rangeSum(nums: number[], n: number, left: number, right: number): number {
  const MOD = 1_000_000_007;
  const heap = new Heap<[number, number]>((a, b) => (a[0] !== b[0] ? a[0] - b[0] : a[1] - b[1]));
  for (let i = 0; i < n; i++) {
    heap.push([nums[i], i]);
  }
 
  let answer = 0;
  for (let mid = 1; mid <= right; mid++) {
    const [num, i] = heap.pop()!;
    if (left <= mid) {
      answer += num;
    }
    if (i + 1 < n) {
      heap.push([num + nums[i + 1], i + 1]);
    }
  }
  return answer % MOD;
}