> 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;
    }
}
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://mayanktyagi3111.gitbook.io/interview-prep/strings-arrays-and-2-pointers/count-of-range-sum.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.