# Range Sum of Sorted Subarray Sums
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/range-sum-of-sorted-subarray-sums)
Canonical: https://scaleengineer.com/dsa/problems/range-sum-of-sorted-subarray-sums
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
---
## Problem
You are given the array `nums` consisting of `n` positive integers. You computed the sum of all non-empty continuous subarrays from the array and then sorted 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 `109 + 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:**

* `n == nums.length`
* `1 <= nums.length <= 1000`
* `1 <= nums[i] <= 100`
* `1 <= left <= right <= n * (n + 1) / 2`

# Approaches
## Brute Force: Generate, Sort, and Sum
This approach directly simulates the process described in the problem. First, we generate all possible non-empty continuous subarray sums. Then, we sort these sums in non-decreasing order. Finally, we iterate through the sorted list from the `left`-th to the `right`-th element (1-indexed) and accumulate their sum.
**Time:** O(n^2 log n) - Generating all subarray sums takes O(n^2). The number of sums is `N = n * (n + 1) / 2`, which is O(n^2). Sorting these `N` sums takes O(N log N) = O(n^2 log(n^2)) = O(n^2 log n). Summing the required range takes O(right - left), which is at most O(n^2). The sorting step dominates the complexity. · **Space:** O(n^2) - We need to store all `n * (n + 1) / 2` subarray sums in a list.
**Pros:** Simple to understand and implement.; Directly follows the problem statement.
**Cons:** Inefficient in both time and space, especially for large `n`.; May result in Time Limit Exceeded or Memory Limit Exceeded for larger constraints.
### Explanation
The simplest way to solve this problem is to follow the instructions literally. We can use two nested loops to generate every possible continuous subarray. The outer loop picks the starting element, and the inner loop expands the subarray to the right. For each subarray, we calculate its sum and store it in a list. After generating all `n * (n + 1) / 2` sums, we sort this list. Finally, we sum up the elements from index `left - 1` to `right - 1` in the sorted list, applying the modulo operation at each addition to handle potentially large sums.

```java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    public int rangeSum(int[] nums, int n, int left, int right) {
        int MOD = 1_000_000_007;
        List<Integer> sums = new ArrayList<>();
        
        for (int i = 0; i < n; i++) {
            int currentSum = 0;
            for (int j = i; j < n; j++) {
                currentSum += nums[j];
                sums.add(currentSum);
            }
        }
        
        Collections.sort(sums);
        
        long result = 0;
        for (int i = left - 1; i < right; i++) {
            result = (result + sums.get(i)) % MOD;
        }
        
        return (int) result;
    }
}
```
### Algorithm
*   Create an empty list, say `sums`, to store all subarray sums.
*   Iterate through the input array `nums` with a starting index `i` from `0` to `n-1`.
*   For each `i`, start a nested loop with an ending index `j` from `i` to `n-1`.
*   Maintain a `currentSum` for the subarray starting at `i`. In the inner loop, add `nums[j]` to `currentSum` and add this `currentSum` to the `sums` list.
*   After generating all `n * (n + 1) / 2` sums, sort the `sums` list in non-decreasing order.
*   Initialize a variable `result` to 0.
*   Iterate from `k = left - 1` to `right - 1` (using 0-based indexing for the list).
*   Add `sums.get(k)` to `result`, taking the modulo `10^9 + 7` at each step to prevent overflow.
*   Return `result`.

## Min-Heap for K-th Smallest Elements
This approach avoids generating and storing all subarray sums at once, which improves space complexity. We can treat the problem as finding elements in a merged list of `n` sorted lists. Each of these `n` lists corresponds to the subarray sums starting at a particular index `i`. Since all numbers in `nums` are positive, for a fixed start `i`, the sums `sum(i,i), sum(i,i+1), ...` form a sorted sequence. A min-heap is a perfect data structure to efficiently extract the smallest element from these `n` lists in sorted order.
**Time:** O(right * log n) - Initializing the heap takes O(n log n). The main loop runs `right` times, and each iteration involves heap operations (poll and offer) which take O(log n) time. The total time is O(n log n + right * log n). In the worst case, `right` is O(n^2), making the complexity O(n^2 log n). · **Space:** O(n) - The priority queue stores at most `n` elements, one for each possible starting index.
**Pros:** Much more space-efficient (O(n)) than the brute-force approach (O(n^2)).; Can be faster in practice if `right` is significantly smaller than `n^2`.
**Cons:** The worst-case time complexity is still high, similar to the brute-force approach.; The logic is more complex to implement than simple generation and sorting.
### Explanation
We use a min-priority queue to keep track of the smallest current subarray sum from each possible starting position. The heap will store an array or object representing `(sum, startIndex, endIndex)`.

We begin by inserting the smallest sum for each starting index `i` (which is just `nums[i]`) into the heap. This means we push `(nums[i], i, i)` for all `i` from `0` to `n-1`.

Then, we iterate `right` times. In each iteration, we extract the minimum sum from the heap. If the iteration count is between `left` and `right`, we add this sum to our total result. After extracting a sum `sum(i, j)`, we generate the next sum from the same starting position `i`, which is `sum(i, j+1)`, and add it back to the heap. This process is repeated until we have found the `right`-th smallest sum.

```java
import java.util.PriorityQueue;

class Solution {
    public int rangeSum(int[] nums, int n, int left, int right) {
        int MOD = 1_000_000_007;
        // Min-heap stores {sum, startIndex, endIndex}
        PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0]));

        // Initial population: sums of subarrays of length 1
        for (int i = 0; i < n; i++) {
            pq.offer(new long[]{nums[i], i, i});
        }

        long result = 0;
        for (int i = 1; i <= right; i++) {
            long[] top = pq.poll();
            long sum = top[0];
            int endIndex = (int) top[2];

            if (i >= left) {
                result = (result + sum) % MOD;
            }

            if (endIndex + 1 < n) {
                long newSum = sum + nums[endIndex + 1];
                pq.offer(new long[]{newSum, top[1], endIndex + 1});
            }
        }

        return (int) result;
    }
}
```
### Algorithm
*   The problem can be viewed as merging `n` sorted lists, where each list `i` contains subarray sums starting at index `i` (`sum(i,i), sum(i,i+1), ...`).
*   Initialize a min-priority queue to store tuples of `(sum, startIndex, endIndex)`.
*   Initially, populate the heap with the first sum from each of the `n` conceptual lists. For each `i` from `0` to `n-1`, push `(nums[i], i, i)` into the heap.
*   Initialize `result = 0`.
*   Loop from `k = 1` to `right`:
    *   Extract the minimum element `(currentSum, startIndex, endIndex)` from the heap.
    *   If `k` is within the range `[left, right]`, add `currentSum` to `result` (modulo `10^9 + 7`).
    *   If the subarray can be extended (i.e., `endIndex + 1 < n`), calculate the next sum for `startIndex`: `newSum = currentSum + nums[endIndex + 1]`. Push `(newSum, startIndex, endIndex + 1)` into the heap.
*   Return `result`.

## Optimal Approach using Binary Search on Answer
This optimal approach reframes the problem. Instead of finding the sum of a range `[left, right]`, we calculate `sum_up_to(right) - sum_up_to(left - 1)`. This reduces the problem to creating a function `calculateSumFirstK(k)` that finds the sum of the `k` smallest subarray sums.

This subproblem can be solved efficiently. We don't need to generate the sums. Instead, we can binary search for the *value* of the `k`-th smallest sum. For any given value `x`, we can count how many subarray sums are less than or equal to `x` in O(n) time using a sliding window. This allows us to find the `k`-th sum's value, `kthSumVal`, in O(n * log(max_sum)) time. Once we have `kthSumVal`, we can calculate the total sum of all subarrays with sums less than `kthSumVal`, and then add the remaining `kthSumVal`s to reach the `k` elements.
**Time:** O(n * log(max_sum)) - The main function `calculateSumFirstK` is called twice. Its complexity is dominated by the binary search, which performs `log(max_sum)` iterations. Each iteration involves a call to an O(n) helper function. `max_sum` is the sum of all elements in `nums`. · **Space:** O(n) - We need O(n) space for the prefix sum and prefix-of-prefix-sum arrays.
**Pros:** Highly efficient with optimal time complexity.; Scales well for large inputs.; Space-efficient, using only O(n) extra space.
**Cons:** The algorithm is significantly more complex to understand and implement correctly.; Requires careful handling of multiple concepts: binary search, sliding window, and advanced prefix sums.
### Explanation
The core idea is to build a function `calculateSumFirstK(nums, n, k)` which is called for `k = right` and `k = left - 1`.

1.  **Find the k-th sum's value:** We binary search for this value. The range of possible sums is from `1` to the total sum of `nums`. For a `mid` value in our binary search, we need to check if it's a potential candidate for the k-th sum. We do this by counting how many subarray sums are less than or equal to `mid`. This count can be found in O(n) using a two-pointer/sliding window approach. Based on this count, we adjust our binary search range. This process gives us `kthSumVal` in O(n * log(max_sum)) time.

2.  **Calculate the final sum:** Now that we have `kthSumVal`, we need the sum of the `k` smallest elements. We first find the sum of all elements strictly smaller than `kthSumVal`. This requires a helper function that, for a given value `v`, returns both the count and sum of subarray sums less than or equal to `v`. This can be done in O(n) using a sliding window combined with prefix sums of prefix sums to calculate the sum of sums within the window in O(1) time. Let this give us `sumSmaller` and `countSmaller` for `v = kthSumVal - 1`. The final sum is `sumSmaller + (k - countSmaller) * kthSumVal`.

```java
class Solution {
    int MOD = 1_000_000_007;

    public int rangeSum(int[] nums, int n, int left, int right) {
        long sumRight = calculateSumFirstK(nums, n, right);
        long sumLeft = calculateSumFirstK(nums, n, left - 1);
        return (int) ((sumRight - sumLeft + MOD) % MOD);
    }

    private long calculateSumFirstK(int[] nums, int n, int k) {
        if (k == 0) return 0;

        int low = 1, high = 0;
        for (int num : nums) high += num;
        int kthSumVal = 0;

        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (countSubarraysWithSumLeq(nums, n, mid) >= k) {
                kthSumVal = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }

        long[] res = getSumAndCountLeq(nums, n, kthSumVal - 1);
        long sumSmaller = res[0];
        long countSmaller = res[1];

        long totalSum = sumSmaller;
        long remainingCount = k - countSmaller;
        totalSum = (totalSum + remainingCount * kthSumVal) % MOD;

        return totalSum;
    }

    private long countSubarraysWithSumLeq(int[] nums, int n, int val) {
        long count = 0;
        long currentSum = 0;
        int left = 0;
        for (int right = 0; right < n; right++) {
            currentSum += nums[right];
            while (currentSum > val) {
                currentSum -= nums[left];
                left++;
            }
            count += (right - left + 1);
        }
        return count;
    }

    private long[] getSumAndCountLeq(int[] nums, int n, int val) {
        long[] prefix = new long[n + 1];
        for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + nums[i];

        long[] prefixOfPrefix = new long[n + 2];
        for (int i = 0; i <= n; i++) prefixOfPrefix[i + 1] = prefixOfPrefix[i] + prefix[i];

        long totalSum = 0;
        long count = 0;
        int left = 0;
        for (int right = 0; right < n; right++) {
            while (prefix[right + 1] - prefix[left] > val) {
                left++;
            }
            int numSubarrays = right - left + 1;
            count += numSubarrays;

            long sumOfPrefixes = prefixOfPrefix[right + 1] - prefixOfPrefix[left];
            totalSum = (totalSum + (long)numSubarrays * prefix[right + 1] - sumOfPrefixes);
        }
        return new long[]{totalSum % MOD, count};
    }
}
```
### Algorithm
*   The problem can be rephrased as `sum_up_to(right) - sum_up_to(left - 1)`.
*   Implement a function `calculateSumFirstK(k)` to find the sum of the `k` smallest subarray sums.
*   **Inside `calculateSumFirstK(k)`:**
    1.  **Find k-th sum value:** Use binary search on the possible range of sums. For a `guess_sum`, we need a helper `countLeq(value)` that counts subarray sums `<= value` in O(n) time using a sliding window. This binary search finds the value of the `k`-th smallest sum, let's call it `kthSumVal`.
    2.  **Calculate total sum:** We need the sum of all subarray sums that are strictly less than `kthSumVal`, and their count. This can be done with another O(n) helper, `getSumAndCountLeq(value)`, which uses a sliding window and prefix sums on prefix sums for O(1) sum calculation within the window.
    3.  Let `(sumSmaller, countSmaller) = getSumAndCountLeq(kthSumVal - 1)`.
    4.  The total sum for the first `k` elements is `(sumSmaller + (k - countSmaller) * kthSumVal) % MOD`.
*   The final answer is `(calculateSumFirstK(right) - calculateSumFirstK(left - 1) + MOD) % MOD`.

# Solutions
### Java

```java
class Solution {
public
  int rangeSum(int[] nums, int n, int left, int right) {
    int[] arr = new int[n * (n + 1) / 2];
    for (int i = 0, k = 0; i < n; ++i) {
      int s = 0;
      for (int j = i; j < n; ++j) {
        s += nums[j];
        arr[k++] = s;
      }
    }
    Arrays.sort(arr);
    int ans = 0;
    final int mod = (int)1 e9 + 7;
    for (int i = left - 1; i < right; ++i) {
      ans = (ans + arr[i]) % mod;
    }
    return ans;
  }
}

```

### JavaScript

```javascript
function rangeSum ( nums , n , left , right ) { let arr = Array (( n * ( n + 1 )) / 2 ). fill ( 0 ); const mod = 10 ** 9 + 7 ; for ( let i = 0 , s = 0 , k = 0 ; i < n ; i ++ , s = 0 ) { for ( let j = i ; j < n ; j ++ , k ++ ) { s += nums [ j ]; arr [ k ] = s ; } } let ans = 0 ; arr = arr . sort (( a , b ) => a - b ). slice ( left - 1 , right ); for ( const x of arr ) { ans += x ; } return ans % mod ; }
```

### Python

```python
class Solution:
    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int: arr = [] for i in range(n): s = 0 for j in range(i, n): s += nums[j] arr . append(s) arr . sort() mod = 10 ** 9 + 7 return sum(arr[left - 1: right]) % mod

```

### CPP

```cpp
class Solution {
public:
  int rangeSum(vector<int> &nums, int n, int left, int right) {
    int arr[n * (n + 1) / 2];
    for (int i = 0, k = 0; i < n; ++i) {
      int s = 0;
      for (int j = i; j < n; ++j) {
        s += nums[j];
        arr[k++] = s;
      }
    }
    sort(arr, arr + n * (n + 1) / 2);
    int ans = 0;
    const int mod = 1e9 + 7;
    for (int i = left - 1; i < right; ++i) {
      ans = (ans + arr[i]) % mod;
    }
    return ans;
  }
};

```