> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/strings-arrays-and-2-pointers/count-of-range-sum.md).

# Count of Range Sum

Given an integer array `nums`, 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` (`i` ≤ `j`), inclusive.

**Note:**\
A naive algorithm of O(n2) is trivial. You MUST do better than that.

**Example:**

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

```java
class Solution {
    int lower, upper;

    public int countRangeSum(int[] nums, int lower, int upper) {
        long[] prefixSum = new long[nums.length + 1];
        this.lower = lower;
        this.upper = upper;
        // PrefixSum[i] -> Sum of first i elements
        for (int i = 1; i <= nums.length; i++)
            prefixSum[i] = prefixSum[i - 1] + nums[i - 1];
        return mergeSort(prefixSum, 0, prefixSum.length - 1);
    }

    private int mergeSort(long[] prefixSum, int start, int end) {
        if (start >= end)
            return 0;
        int mid = start + (end - start) / 2;
        // The pairs in the left half and the pairs in the 
        // right half get counted in the recursive calls.
        int leftAns = mergeSort(prefixSum, start, mid);
        int rightAns = mergeSort(prefixSum, mid + 1, end);
        // We just need to also count the pairs that use both halves.
        return leftAns + rightAns + merge(prefixSum, start, end);
    }

    private int merge(long[] prefixSum, int start, int end) {
        int ans = 0, mid = start + (end - start) / 2;
        long[] temp = new long[end - start + 1];
        int pointer1 = start, pointer2 = mid + 1, index = 0;
        int left = mid + 1, right = mid + 1;
        // O(N), because "left" & "right" variables only move right
        while (pointer1 <= mid) {
            // We find a limit, such that we just enter "lower" limit
            while (left <= end && prefixSum[left] - prefixSum[pointer1] < lower)
                left++;
            // We find a limit, such that we just get out of "upper" limit
            while (right <= end && prefixSum[right] - prefixSum[pointer1] <= upper)
                right++;
            // Normal merging process
            while (pointer2 <= end && prefixSum[pointer2] < prefixSum[pointer1])
                temp[index++] = prefixSum[pointer2++];
            temp[index++] = prefixSum[pointer1++];
            // Answer will be [L,R], L is shown by pointer1, & 
            // R is shown by all the values in between [left,right)
            ans += right - left;
        }
        while (pointer2 <= end)
            temp[index++] = prefixSum[pointer2++];
        for (int i = start; i <= end; i++)
            prefixSum[i] = temp[i - start];
        return ans;
    }
}
```