1
/**
2
 * @param {number[]} nums
3
 * @param {number} n
4
 * @param {number} left
5
 * @param {number} right
6
 * @return {number}
7
 */
8
var rangeSum = function (nums, n, left, right) {
9
  var len = nums.length;
10

11
  var prefix = [nums[0]];
12
  function buildPrefix() {
13
    for (var i = 1; i < len; i++) {
14
      prefix[i] = prefix[i - 1] + nums[i];
15
    }
16
  }
17

18
  buildPrefix();
19

20
  function countUnderSum(sum, cb) {
21
    var left = 0;
22
    var count = 0;
23
    var right = 0;
24

25
    while (right < len) {
26
      let wholeSubSum = prefix[right] - (left === 0 ? 0 : prefix[left - 1]);
27
      if (wholeSubSum <= sum) {
28
        count += right - left + 1;
29
        cb && cb(left, right);
30
      } else {
31
        while (wholeSubSum > sum) {
32
          if (left <= right) {
33
            wholeSubSum -= nums[left];
34
            left++;
35
          } else {
36
            break;
37
          }
38
        }
39
        count += right - left + 1;
40
        cb && cb(left, right);
41
      }
42
      right++;
43
    }
44

45
    return count;
46
  }
47

48
  function calSubArraySumByRange(i, j) {
49
    var windowLen = j - i + 1;
50
    var sum = 0;
51
    while (windowLen > 0) {
52
      sum += nums[j] * windowLen;
53
      windowLen--;
54
      j--;
55
    }
56
    return sum;
57
  }
58

59
  function calSum(count) {
60
    var lowSum = findTheLowestSumThatSatisfyTheSpecficCount(count);
61
    var sum = 0;
62
    countUnderSum(lowSum, (i, j) => {
63
      sum += calSubArraySumByRange(i, j);
64
    });
65

66
    //This line is used to deal with some same value cases
67
    //Such as if the low value is 9, and we have 9 subarrays of which low value
68
    //is 9. But the count is 8, so we must remove one of it.
69
    return sum - (countUnderSum(lowSum) - count) * lowSum;
70
  }
71

72
  function findTheLowestSumThatSatisfyTheSpecficCount(count) {
73
    var l = 0;
74
    var r = prefix[len - 1];
75
    while (l < r) {
76
      var mid = Math.floor((l + r) / 2);
77
      if (countUnderSum(mid) < count) {
78
        l = mid + 1;
79
      } else {
80
        r = mid;
81
      }
82
    }
83

84
    return l;
85
  }
86

87
  return (calSum(right) - calSum(left - 1)) % (Math.pow(10, 9) + 7);
88
};