1
class Solution {
2
 public:
3
  int rangeSum(vector<int> &nums, int n, int left, int right) {
4
    const int m = 1e9 + 7;        // To return ans % m
5
    int ans = 0;                  // Final Answer
6
    int k = 1;                    // For 1 based indexing
7
    int size = (n * (n + 1)) / 2; // We can form n(n+1)/2 subarrays for an array of size n
8
    vector<int> subsum(size + 1);
9
    for (int i = 0; i < n; i++) {
10
      int sum = 0;
11
      for (int j = i; j < n; j++) {
12
        sum += nums[j];    // Sum of the subarray
13
        subsum[k++] = sum; // Inserting the prefix sum at the index
14
      }
15
    }
16
    sort(subsum.begin(), subsum.end()); // Sorting the array
17
    for (int i = left; i <= right; i++) {
18
      ans = (ans + subsum[i]) % m; // ans modulo 10^9 +7
19
    }
20
    return ans;
21
  }
22
};