← DSA Atlas
Dedicated problem page · #327

Count of Range Sum

HardAdvanced Range Data StructuresCount prefix-sum pairs in rangeMerge sort counting on prefix sums
Solve on LeetCode ↗
327
HardAdvanced Range Data StructuresMerge sort counting on prefix sumsCount prefix-sum pairs in range

Count of Range Sum

Given an integer array nums and two integers lower and upper, return the number of range sums that lie in [lower, upper] inclusive. A range sum S(i, j) is the sum of nums[i..j] for i <= j.

Open official problem prompt ↗
In plain English

Count how many contiguous subarrays have a sum that falls inside a given inclusive band [lower, upper].

Picture it like this

Track a running bank balance after each transaction. A subarray's sum is the difference between two balances; you want to count balance pairs that grew by an amount between lower and upper. Sorting balances lets you slide a window to count matches fast.

Example
Input
nums = [-2,5,-1], lower = -2, upper = 2
Output
3
Why
The qualifying ranges are [0,0]=-2, [2,2]=-1, and [0,2]=2, all within [-2,2].
Constraints
1 <= nums.length <= 10^5-2^31 <= nums[i] <= 2^31 - 1-10^5 <= lower <= upper <= 10^5Answer fits in a 32-bit integer
Pattern lesson

See the pattern, then code

Count prefix-sum pairs in range
Recognition clue

A range sum equals prefix[j+1] - prefix[i]; counting range sums within a band becomes counting prefix-sum pairs whose difference lies in [lower, upper], a merge-sort counting task.

↗
Advanced Range Data Structures

Online prefix or range queries with updates, inversions, or coordinate compression.. Build prefix sums P. A range sum in [lower, upper] means lower <= P[j] - P[i] <= upper for i < j. During a merge sort of P, count for each left-half value how many right-half values fall in the valid window.

New words, made simpleKnow these before the algorithm
Prefix sum
P[k] is the sum of the first k elements, so subarray (i, j) sums to P[j+1] - P[i].
Two-pointer window
Two indices j and k that bracket the right-half values satisfying the lower and upper bounds for a fixed left value.
Merge-sort counting
Counting cross-half qualifying pairs while the halves are still individually sorted, before merging.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
All subarray sums

Quadratic; fails at n = 10^5.

Enumerate every (i, j) and test its sum against the band.

Time O(n^2)Space O(1)
Best choicePrefix + merge sort

Efficient and robust to large or negative values.

Reduce to counting prefix pairs with difference in range, counted during merge sort.

Time O(n log n)Space O(n)
Prefix + BIT over compressed sums

Also works but needs careful coordinate compression of P, lower, upper offsets.

Insert prefix sums into a Fenwick tree and range-query the valid band.

Time O(n log n)Space O(n)
The rule we keep true

Invariant

Before merging two halves, count already includes every qualifying pair fully inside a half; the merge step then adds exactly the cross-boundary pairs where the left index comes from the lower half and the right index from the upper half.

Why this is correct

Reasoning

Every subarray corresponds to a unique ordered prefix pair (i, j) with i < j, and merge sort visits each such cross-half pair once as the recursion boundary. Because both halves are sorted by value, the window [j, k) of right-half prefixes satisfying lower <= P[right] - P[left] <= upper is contiguous and its pointers only advance, giving linear counting per merge level.

The algorithm in three movesSay these aloud before coding
1Compute prefix sums P of length n+1 with P[0]=0

P = [0,-2,3,2]

2Recursively merge-sort P by value

left half [0,-2], right half [3,2]

3During each merge, for every left element advance two pointers to bound P[j] in [left+lower, left+upper]

for left=0: j..k window over {2,3}

4Add the width of that window to the count

total qualifying = 3

5Sort the current slice and return the accumulated count

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
00
-21
32
23
1 · Readnums=[-2,5,-1]
2 · AskWhat is P?
3 · Update stateP = [0,-2,3,2]
4 · Result4 prefix values
Key takeaway

Prefix sums P; counting pairs P[j]-P[i] within [lower,upper] across the merge boundary.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 5-7Prefix sums

    P[0]=0 lets range (0, j) be expressed as P[j+1]-P[0].

  2. 2
    Lines 9-13Recurse halves

    Count pairs within each half first, then handle the boundary.

  3. 3
    Lines 14-19Slide the window

    For each left value, j finds the first right value with difference >= lower and k the first exceeding upper; k-j counts valid right values.

  4. 4
    Lines 20Merge slice

    Sorting the slice keeps the invariant that halves are sorted for the parent merge.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • Single element array counts that one range if it lies in the band
  • All negative numbers with a negative band
  • lower == upper counts only exact sums
  • Large values near 2^31 are fine in Python integers, no overflow
!

Common beginner mistakes

  • Using strict inequalities and missing the inclusive endpoints (must be < lower and <= upper for the two pointers)
  • Resetting the j, k pointers per left value instead of letting them advance monotonically
  • Forgetting the P[0]=0 sentinel, which drops all ranges starting at index 0
  • Sorting the whole prefix array up front, which destroys the index ordering needed to count pairs
Check your understanding

Why must j and k advance monotonically and never reset as we iterate over left-half values?

More in Advanced Range Data Structures

#218The Skyline ProblemSweep line with max-heap#307Range Sum Query – MutablePoint update, prefix-sum query#315Count of Smaller Numbers After SelfCount smaller to the right#493Reverse PairsCount significant inversions#699Falling SquaresRange assign, range max#715Range ModuleMerge and split disjoint intervals