Count of Range Sum

Count subarrays whose sum falls within a given inclusive range.

prefix-sum merge-sort divide-conquer counting range-sum

Write a function `count_range_sum(nums, lower, upper)` that takes a list of integers `nums` and two integers `lower` and `upper` (with `lower <= upper`), and returns the number of non-empty contiguous subarrays whose sum is in the inclusive range `[lower, upper]`.

A subarray is defined by start index `i` and end index `j` (0 <= i <= j < len(nums)). The sum of a subarray is `nums[i] + nums[i+1] + ... + nums[j]`.

You must implement an efficient algorithm. A naive O(n^2) solution will likely time out for large inputs. Aim for O(n log n) time and O(n) space.

### Function Signature
```python
def count_range_sum(nums, lower, upper):
    pass
```

### Input
- `nums`: list of integers, possibly negative. Length `n` satisfies `0 <= n <= 1000` in the auto-grader, but design for up to 10^5.
- `lower`, `upper`: integers with `lower <= upper`.

### Output
- An integer: the count of subarrays whose sum is between `lower` and `upper` inclusive.

### Notes
- A subarray with sum exactly `lower` or `upper` is counted.
- If `nums` is empty, return 0.

Constraints

- 0 <= len(nums) <= 1000 in the tests (but the algorithm should handle up to 10^5).
- Each element satisfies -10^9 <= nums[i] <= 10^9.
- -10^9 <= lower <= upper <= 10^9.
- The answer fits in a 64-bit integer.

Example

>>> count_range_sum([-2, 5, -1], -2, 2)
3
>>> count_range_sum([0, 0], 0, 0)
3
>>> count_range_sum([1, 2, 3], 1, 3)
4
>>> count_range_sum([], -1, 1)
0

35 points ~40 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Compute prefix sums where prefix[i] = sum of nums[0:i]. Then subarray sum from i to j-1 is prefix[j] - prefix[i].

Use a divide-and-conquer approach: split the prefix array, recursively count valid pairs crossing the midpoint, and merge the two halves in sorted order.

For the crossing count, use two pointers over the right half to find for each left prefix the range of right prefixes that satisfy lower <= right - left <= upper.

The merge step can be done in-place or with a temporary array using a standard merge sort template.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.