We need to count how many contiguous subarrays have a sum that falls within the range [lower, upper]. A range sum S(i, j) is the sum of elements from index i to index j.

A brute force checks every pair (i, j) and computes the subarray sum, which is too slow at this input size.

Prefix sums reframe the problem. If we define prefix[0] = 0 and prefix[k] = nums[0] + nums[1] + ... + nums[k-1], then the range sum S(i, j) = prefix[j+1] - prefix[i]. So the problem becomes: for how many pairs (i, j) with i < j does lower <= prefix[j] - prefix[i] <= upper hold? This is an inversion-counting variant on the prefix sum array.

Key Constraints:

Intuition

Compute every possible range sum and check whether it falls within [lower, upper]. Prefix sums reduce each sum computation from O(n) to O(1), but we still enumerate all O(n^2) pairs.

Build a prefix sum array where prefix[i] stores the sum of nums[0..i-1]. Then the sum of any subarray nums[i..j] equals prefix[j+1] - prefix[i]. Now iterate over all pairs (i, j) with 0 <= i < j <= n and count how many satisfy lower <= prefix[j] - prefix[i] <= upper.

Algorithm

Example Walkthrough

Code

This is too slow for the given constraints. The next approach sorts the prefix sums while counting, so that for each prefix sum we can find how many earlier ones produce a valid difference without scanning them all.

Intuition

Merge sort counts pairs during the merge step: both halves are already sorted at that point, which lets two pointers count valid pairs in O(n) instead of O(n^2).

We need to count pairs (i, j) where i < j and lower <= prefix[j] - prefix[i] <= upper. Rearranging, for a fixed j we need prefix sums from the left half that satisfy prefix[j] - upper <= prefix[i] <= prefix[j] - lower.

When merging two sorted halves, every element in the right half originally came after every element in the left half, so any left-right pairing satisfies i < j by construction. For each element in the right half, two pointers locate the range of valid elements in the sorted left half. Because the right half is also sorted, the query window [prefix[j] - upper, prefix[j] - lower] only shifts upward as j advances, so both pointers move forward monotonically and the total counting work is O(n) per merge level.

Algorithm

Visualization and Code

Merge sort reaches O(n log n) by interleaving counting with sorting. An alternative keeps the prefix sums in their original order and maintains a data structure that answers "how many values seen so far fall in range [a, b]" in O(log n).

Intuition

Instead of divide and conquer, we can take an online approach. Process prefix sums from left to right. For each new prefix[j], count how many previously inserted prefix[i] values satisfy prefix[j] - upper <= prefix[i] <= prefix[j] - lower. This is a range count query on the values seen so far, and because we query before inserting prefix[j], only prefix[0] through prefix[j-1] are counted, which enforces i < j.

A Binary Indexed Tree (also called a Fenwick Tree) supports point updates and prefix sum queries in O(log n). To count values in a range [a, b], we compute prefixCount(b) - prefixCount(a-1). Prefix sums can have magnitude up to n * 2^31, so the BIT cannot be indexed by raw values. We use coordinate compression: collect all values we will ever query or insert, sort them, and map them to consecutive integers 1, 2, 3, ...

For each prefix[j], we insert prefix[j] and query the range [prefix[j] - upper, prefix[j] - lower]. So we collect all prefix sums and all the boundary values prefix[j] - upper and prefix[j] - lower, sort and deduplicate them, then map them to BIT indices.

Algorithm

Example Walkthrough

Code