> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Count of Range Sum Python Solution with Tests

> Tested Python solution for LeetCode 327 with 23 pytest cases. Generate a practice environment with lcpy.

LeetCode 327, [Hard](/catalog/hard). Topics: [Array](/catalog/topics/array), [Binary Search](/catalog/topics/binary-search), [Divide and Conquer](/catalog/topics/divide-and-conquer), [Binary Indexed Tree](/catalog/topics/binary-indexed-tree), [Segment Tree](/catalog/topics/segment-tree), Merge Sort, [Ordered Set](/catalog/topics/ordered-set). [View on LeetCode](https://leetcode.com/problems/count-of-range-sum/description/).

Generate this problem as a practice environment: tested reference solution, 23 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 327   # by problem number
lcpy gen -s count_of_range_sum   # by problem name
```

## Problem

\<p>Given an integer array \<code>nums\</code> and two integers \<code>lower\</code> and \<code>upper\</code>, return \<em>the number of range sums that lie in\</em> \<code>\[lower, upper]\</code> \<em>inclusive\</em>.\</p>

\<p>Range sum \<code>S(i, j)\</code> is defined as the sum of the elements in \<code>nums\</code> between indices \<code>i\</code> and \<code>j\</code> inclusive, where \<code>i \<= j\</code>.\</p>

### Examples

```
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.
```

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

### Constraints

\<ul>
\<li>\<code>1 \<= nums.length \<= 10\<sup>5\</sup>\</code>\</li>
\<li>\<code>-2\<sup>31\</sup> \<= nums\[i] \<= 2\<sup>31\</sup> - 1\</code>\</li>
\<li>\<code>-10\<sup>5\</sup> \<= lower \<= upper \<= 10\<sup>5\</sup>\</code>\</li>
\<li>The answer is \<strong>guaranteed\</strong> to fit in a \<strong>32-bit\</strong> integer.\</li>
\</ul>

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/count_of_range_sum/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/count_of_range_sum/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class Solution:
    # Time: O(n log n)
    # Space: O(n)
    def count_range_sum(self, nums: list[int], lower: int, upper: int) -> int:
        prefix = [0]
        for value in nums:
            prefix.append(prefix[-1] + value)

        def sort_count(left: int, right: int) -> int:
            if right - left <= 1:
                return 0
            mid = (left + right) // 2
            count = sort_count(left, mid) + sort_count(mid, right)
            low_part = sorted(prefix[left:mid])
            high_part = sorted(prefix[mid:right])
            start = end = 0
            for value in low_part:
                while start < len(high_part) and high_part[start] - value < lower:
                    start += 1
                while end < len(high_part) and high_part[end] - value <= upper:
                    end += 1
                count += end - start
            merged: list[int] = []
            i = j = 0
            while i < len(low_part) and j < len(high_part):
                if low_part[i] <= high_part[j]:
                    merged.append(low_part[i])
                    i += 1
                else:
                    merged.append(high_part[j])
                    j += 1
            merged.extend(low_part[i:])
            merged.extend(high_part[j:])
            prefix[left:right] = merged
            return count

        return sort_count(0, len(prefix))
```

## Complexity

| Time | Space |
| - | - |
| O(n log n) | O(n) |

## Tags


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.