Problem Explanation

Given an array consisting of positive integers, we are to compute the sum of all non-empty continuous subarrays. The subarrays are computed such that the element of each subarray would be distinct and sorted in non-decreasing order after which a new array is created. The problem is to find the sum of the numbers from index left to index right in the newly sorted array. Given the number can be extremely large, we are to output the result modulo 1,000,000,007.

To find the solution, the algorithm we would implement is the Binary Search Technique in order to find the first K Subarray Sums. A helper function will be used to compute the sum of subarrays that don't exceed the given limit and the number of these subarrays. To compute these subarrays, a moving window technique is used. For each subarray, we will keep track of the current sum and add the product of the number of elements and its last element to this sum. If the window sum exceeds the limit, the window is shrunk from the left side.

For example, given Nums = [1, 2, 3, 4, 5], Left = 1, Right = 5, the result should be 21

Python Solution

1
2python
3class Solution:
4    def rangeSum(self, nums, n, left, right) -> int:
5        kMod = 1_000_000_007
6        def subarraysAndSumNoGreaterThan(m):
7            count = 0
8            total = 0
9            sum = 0
10            window = 0
11            i = 0
12            j = 0
13            while j < n:
14                sum += nums[j] * (j - i + 1)
15                window += nums[j]
16                while window > m:
17                    sum -= window
18                    window -= nums[i]
19                    i += 1
20                count += j - i + 1
21                total += sum
22                j += 1
23            return count, total
24        # L, R is the possible range of the sum of any subarray
25        L = min(nums)
26        R = sum(nums)
27        def firstKSubarraysSum(k) -> int:
28            l = L
29            r = R
30            while l < r:
31                m = l + (r - l) // 2
32                if subarraysAndSumNoGreaterThan(m)[0] < k:
33                    l = m + 1
34                else:
35                    r = m
36            count, total = subarraysAndSumNoGreaterThan(l)
37            return total - l * (count - k)
38        return (firstKSubarraysSum(right) - firstKSubarraysSum(left - 1)) % kMod

Citation

This problem is referenced from https://leetcode.com/problems/range-sum-of-sorted-subarray-sums/.# JavaScript Solution

The JavaScript solution uses similar logic to the Python solution, utilizing a binary search technique to find the first K subarray sums. A helper function getSubarraysSumNoGreaterThan(target) is used to calculate the sum of all the subarray sums and the number of these subarrays that do not exceed the target.

1
2javascript
3class Solution {
4    rangeSum(nums, n, left, right) {
5        const MOD = 1e9 + 7;
6        let prefixSum = new Array(n + 1).fill(0);
7        for (let i = 1; i <= n; i++) {
8            prefixSum[i] = prefixSum[i - 1] + nums[i - 1];
9        }
10
11        let getSubarraysSumNoGreaterThan = (target) => {
12            let subarraysSum = 0, curSum = 0;
13            let count = 0, j = 1;
14            for (let i = 1; i <= n; i++) {
15                while (j <= n && prefixSum[j] - prefixSum[i - 1] <= target) {
16                    curSum += prefixSum[j] - prefixSum[i - 1];
17                    j++;
18                }
19                subarraysSum += curSum + (j - i) * (prefixSum[i - 1] - target);
20                subarraysSum %= MOD;
21                count += j - i;
22                curSum -= prefixSum[j - 1] - prefixSum[i];
23            }
24            return {count, subarraysSum};
25        }
26
27        let firstKSubarraysSum = (k) => {
28            let l = Math.min(...nums), r = prefixSum[n], m;
29            while (l < r) {
30                m = l + ((r - l) >> 1);
31                let {count, subarraysSum} = getSubarraysSumNoGreaterThan(m);
32                if (count < k) {
33                    l = m + 1;
34                } else {
35                    r = m;
36                    res = subarraysSum;
37                }
38            }
39            return res;
40        }
41        return (firstKSubarraysSum(right) - firstKSubarraysSum(left - 1) + MOD) % MOD;
42    }
43}

Java Solution

Below is the Java version of this solution:

1
2java
3import java.util.PriorityQueue;
4import java.util.Queue;
5
6public class Solution {
7    private static final int MODULO = 1_000_000_007;
8
9    public int rangeSum(int[] nums, int n, int left, int right) {
10        Queue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
11        for (int i = 0; i < n; i++) {
12            pq.offer(new int[]{nums[i], i + 1});
13        }
14        int sum = 0;
15        for (int i = 1; i <= right; i++) {
16            int[] entry = pq.poll();
17            if (i >= left) {
18                sum = (sum + entry[0]) % MODULO;
19            }
20            if (entry[1] < n) {
21                pq.offer(new int[]{entry[0] + nums[entry[1]], entry[1] + 1});
22            }
23        }
24        return sum;
25    }
26}

In the Java solution, we utilize a PriorityQueue to keep track of the sums of the subarrays. For each number, we put it and its next index into the queue. For each smallest sum, we remove it from the queue, add it to the total sum if it's in the range, and add the next sum into the queue if possible. The sum is then returned modulo 1,000,000,007 to prevent overflow.