Given an integer array nums and two integers lower and upper, return the number of range sums that lie in [lower, upper] inclusive.

Range sum S(i, j) is defined as the sum of the elements in nums between indices i and j inclusive, where i &lt;= j.

&nbsp;
Example 1:

Input: nums = [-2,5,-1], lower = -2, upper = 2
Output: 3
Explanation: The three ranges are: [0,0], [2,2], and [0,2] and their respective sums are: -2, -1, 2.


Example 2:

Input: nums = [0], lower = 0, upper = 0
Output: 1


&nbsp;
Constraints:


	1 &lt;= nums.length &lt;= 105
	-231 &lt;= nums[i] &lt;= 231 - 1
	-105 &lt;= lower &lt;= upper &lt;= 105
	The answer is guaranteed to fit in a 32-bit integer.


class Solution:
    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:
        acc = list(accumulate(nums))
        ans = a = 0
        for n in nums:
            a += n
            ans += sum(1 for x in acc if lower <= x <= upper)
            acc.pop(0)
            lower += n
            upper += n
        return ans
class Solution {
    public int countRangeSum(int[] nums, int lower, int upper) {
        int n = nums.length, ans = 0;
        long[] pre = new long[n+1];
        for (int i = 0; i < n; i++){
            pre[i+1] = nums[i] + pre[i];
        }
        Arrays.sort(pre);
        int[] bit = new int[pre.length+2];
        long sum = 0;
        for (int i = 0; i < n; i++){
            update(bit, bs(sum, pre), 1);
            sum += nums[i];
            ans += sum(bit, bs(sum-lower, pre)) - sum(bit, bs(sum-upper-1, pre));
        }
        return ans;
    }

    private int bs(long sum, long[] pre){ // return the index of first number bigger than sum
        int lo = 0, hi = pre.length;
        while(lo < hi){
            int mid = (lo+hi) >> 1;
            if (pre[mid]>sum){
                hi=mid;
            }else{
                lo=mid+1;
            }
        }
        return lo;
    }

    private void update(int[] bit, int idx, int inc){
        for (++idx; idx < bit.length; idx += idx & -idx){
            bit[idx] += inc;
        }
    }

    private int sum(int[] bit, int idx){
        int ans = 0;
        for (++idx; idx > 0; idx -= idx & -idx){
            ans += bit[idx];
        }
        return ans;
    }
}
class Solution {
public:
    using ll = long long;

    int countRangeSum(vector<int>& nums, int lower, int upper) {
        // Build prefix sums
        vector<ll> prefixSums(nums.size() + 1, 0);
        for (int i = 0; i < nums.size(); i++) {
            prefixSums[i + 1] = prefixSums[i] + nums[i];
        }

        // Run merge sort and count range sum along the way
        tempNums.assign(prefixSums.size(), 0);
        splitAndMerge(prefixSums, 0, prefixSums.size(), lower, upper);

        return count;
    }

    void splitAndMerge(vector<ll> &nums, const int left, const int right, const int lower, const int upper) {
        if (right - left <= 1) return;
        const int mid = left + (right - left) / 2;
        splitAndMerge(nums, left, mid, lower, upper);
        splitAndMerge(nums, mid, right, lower, upper);

        countRangeSums(nums, left, mid, right, lower, upper);

        merge(nums, left, mid, right);
    }

    void countRangeSums(const vector<ll> &prefixSums, const int left, const int mid, const int right, const int lower, const int upper) {
        // S(i,j) == prefixSums[j+1] - prefixSums[i] (i <= j)
        // S(i,j) == prefixSums[k] - prefixSums[i] (let k=j+1, i < k)
        //
        // lower <= S(i,j) <= upper
        // => lower <= prefixSums[k] - prefixSums[i] <= upper
        // => lower + prefixSums[i] <= prefixSums[k] <= upper + prefixSums[i]
        for (int i = left; i < mid; i++) {
            const ll newLower = lower + prefixSums[i];
            const ll newUpper = upper + prefixSums[i];
            const auto findStart = prefixSums.begin() + mid;
            const auto findEnd = prefixSums.begin() + right;
            const auto itFoundLower = std::lower_bound(findStart, findEnd, newLower);
            const auto itFoundUpper = std::upper_bound(findStart, findEnd, newUpper);
            count += (itFoundUpper - itFoundLower);
        }
    }

    void merge(vector<ll> &nums, const int left, const int mid, const int right) {
        std::copy(nums.begin() + left, nums.begin() + right, tempNums.begin() + left);
        int i = left, j = mid;
        for (int k = left; k < right; k++) {
            if (i < mid && j < right) {
                if (tempNums[i] < tempNums[j]) {
                    nums[k] = tempNums[i++];
                } else {
                    nums[k] = tempNums[j++];
                }
            } else if (i >= mid) {
                nums[k] = tempNums[j++];
            } else { // j >= right
                nums[k] = tempNums[i++];
            }
        }
    }

    vector<ll> tempNums;
    int count = 0;
};
var countRangeSum = function(nums, lower, upper) {
  let preSum = Array(nums.length + 1).fill(0);
  let count = 0;

  // create preSum array, use preSum to check the sum range
  for (let i = 0; i < nums.length; i++) {
      preSum[i + 1] = preSum[i] + nums[i];
  }

  const sort = function(preSum) {
      if (preSum.length === 1) return preSum;

      let mid = Math.floor(preSum.length / 2);
      let left = sort(preSum.slice(0, mid));
      let right = sort(preSum.slice(mid))

      return merge(left, right);
  }

  const merge = function(left, right) {
      let start = 0;
      let end = 0;

      for (let i = 0; i < left.length; i++) {
          // all elements before start index, after subtracting left[i] are less than lower, which means all elements after start index are bigger or equal than lower
          while (start < right.length && right[start] - left[i] < lower) {
              start++;
          }
          // similarly, all elements before end index are less or euqal then upper
          while (end < right.length && right[end] - left[i] <= upper) {
              end++;
          }

          // since the initial values of start and end are the same, and upper >= lower, so end will >= start too, which means the rest of the end minus start element difference will fall between [lower, upper].
          count += end - start;
      }

      let sort = [];
      while (left.length && right.length) {
          if (left[0] <= right[0]) {
              sort.push(left.shift());
          } else {
              sort.push(right.shift());
          }
      }

      return [...sort, ...left, ...right];
  }

  sort(preSum);
  return count;
};
Count of Range Sum