Count of Range Sum — Merge Sort, Fenwick Tree & Prefix Sum Counting

Problem Statement#

LeetCode 327 — Count of Range Sum | Difficulty: Hard

Given an integer array nums and two integers lower and upper, return the number of range sums that fall in the inclusive interval [lower, upper].

A range sum S(i, j) is the sum of nums[i], nums[i+1], ..., nums[j] for i less than or equal to j.

Constraints:

• 1 is less than or equal to nums.length, which is less than or equal to 10^5
• -2^31 is less than or equal to nums[i], which is less than or equal to 2^31 minus 1
• -10^5 is less than or equal to lower, which is less than or equal to upper, which is less than or equal to 10^5
• The answer is guaranteed to fit in a 32-bit integer

Example 1:

Input:  nums = [-2, 5, -1], lower = -2, upper = 2
Output: 3
Explanation:
  S(0,0) = -2  in [-2, 2]
  S(2,2) = -1  in [-2, 2]
  S(0,2) = 2   in [-2, 2]

Example 2:

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

Why This Problem Matters#

Count of Range Sum is the most elegant LeetCode Hard for divide-and-conquer counting on prefix sums. Google, Meta, and Bloomberg use it as a senior interview because it tests the prefix-sum reformulation, the merge-sort counting trick, and the Fenwick-tree-with-coordinate-compression alternative — three independent senior-level techniques in one problem.

The brute force is O(n^2) — compute every subarray sum and test the condition. With n up to 10^5, that is 10^10 operations: hopeless. Reaching O(n log n) requires you to spot that range sums equal differences of prefix sums, then count pairs of prefix sums whose difference falls in [lower, upper]. This is the exact same family of "count pairs satisfying a condition" problems as Reverse Pairs and Count Smaller After Self.

The Core Insight#

Define the prefix-sum array P of length n + 1:

P[0] = 0, P[k] = nums[0] + nums[1] + ... + nums[k-1]

Then S(i, j) = P[j+1] - P[i]. The condition lower is less than or equal to S(i, j) is less than or equal to upper becomes:

lower is less than or equal to P[j+1] - P[i] is less than or equal to upper

Equivalently, for each prefix index j, count how many prefix indices i less than j satisfy:

P[j] - upper is less than or equal to P[i] is less than or equal to P[j] - lower

That is a range count over already-seen prefix sums. Two structures solve it in O(n log n):

Approach A — Modified Merge Sort#

Sort the prefix sums via merge sort. During merge of left and right halves, every pair (i, j) with i in left and j in right already satisfies i less than j. For each j, two pointers sweep left to find the count of P[i] in the target range — O(n) per merge level, O(n log n) total.

Approach B — Fenwick Tree on Compressed Prefix Sums#

Coordinate-compress the union of P, P + lower, and P + upper to dense ranks. Sweep P left to right. At each step, query the count of seen ranks in [rank(P[j] - upper), rank(P[j] - lower)], then insert P[j].

Both run in O(n log n). Merge sort is the cleaner write-up; Fenwick generalizes more easily.

A subtle pitfall: the prefix sums can exceed 2^31 (because individual nums[i] can be near INT_MAX). Use 64-bit integers consistently.

Visual Dry Run#

Trace nums = [-2, 5, -1], lower = -2, upper = 2.

Prefix sums: P = [0, -2, 3, 2]   (length n+1 = 4)
 
For each j = 1, 2, 3, count i < j with P[j] - upper <= P[i] <= P[j] - lower:
 
j=1, P[1]=-2:  bounds = [-2 - 2, -2 - (-2)] = [-4, 0]
              prior P values: [0]
              0 in [-4, 0]?  yes  -> count += 1   total = 1
 
j=2, P[2]=3:   bounds = [3 - 2, 3 - (-2)] = [1, 5]
              prior P values: [0, -2]
              0 in [1, 5]?   no
              -2 in [1, 5]?  no
              -> count += 0  total = 1
 
j=3, P[3]=2:   bounds = [2 - 2, 2 - (-2)] = [0, 4]
              prior P values: [0, -2, 3]
              0 in [0, 4]?   yes
              -2 in [0, 4]?  no
              3 in [0, 4]?   yes
              -> count += 2  total = 3

The answer is 3, matching the brute-force enumeration.

Solution (Optimal)#

Python — Modified Merge Sort#

from typing import List
 
class Solution:
    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:
        # build prefix sums of length n+1
        prefix = [0]
        for x in nums:
            prefix.append(prefix[-1] + x)              # use Python's arbitrary-precision ints
 
        def merge_sort(lo: int, hi: int) -> int:
            if hi - lo <= 1:
                return 0                               # single element or empty -> no pairs
            mid = (lo + hi) // 2
            count = merge_sort(lo, mid) + merge_sort(mid, hi)
 
            # count pairs (i, j) with i in left, j in right
            # condition: prefix[j] - prefix[i] in [lower, upper]
            j_lo = j_hi = mid
            for i in range(lo, mid):
                # j_lo: smallest j with prefix[j] - prefix[i] >= lower
                while j_lo < hi and prefix[j_lo] - prefix[i] < lower:
                    j_lo += 1
                # j_hi: smallest j with prefix[j] - prefix[i] > upper
                while j_hi < hi and prefix[j_hi] - prefix[i] <= upper:
                    j_hi += 1
                count += j_hi - j_lo                   # all j in [j_lo, j_hi) satisfy condition
 
            # standard merge step (preserves sorted prefix array slice)
            prefix[lo:hi] = sorted(prefix[lo:hi])
            return count
 
        return merge_sort(0, len(prefix))

Python — Fenwick Tree (Alternative)#

from typing import List
from bisect import bisect_left, bisect_right
 
class Solution:
    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:
        # build prefix sums
        prefix = [0]
        for x in nums:
            prefix.append(prefix[-1] + x)
 
        # coordinate compress over the union of {P[i], P[i]+lower, P[i]+upper}
        # (we need the bounds queryable in the same rank space)
        coords = sorted({p for p in prefix} |
                        {p - upper - 1 for p in prefix} |
                        {p - lower for p in prefix})
        rank = {v: i + 1 for i, v in enumerate(coords)}    # 1-indexed
        size = len(coords)
        bit = [0] * (size + 1)
 
        def update(i: int) -> None:
            while i <= size:
                bit[i] += 1
                i += i & (-i)
 
        def query(i: int) -> int:
            s = 0
            while i > 0:
                s += bit[i]
                i -= i & (-i)
            return s
 
        ans = 0
        # process prefix sums in order; for each P[j], count prior P[i] in [P[j]-upper, P[j]-lower]
        for p in prefix:
            lo_r = rank[p - upper - 1]                     # one below lower bound
            hi_r = rank[p - lower]                         # at upper bound
            ans += query(hi_r) - query(lo_r)
            update(rank[p])
        return ans

JavaScript — Modified Merge Sort#

var countRangeSum = function(nums, lower, upper) {
    // BigInt prefix sums to avoid 64-bit overflow on adversarial inputs
    const prefix = [0n];
    for (const x of nums) prefix.push(prefix[prefix.length - 1] + BigInt(x));
 
    const lo64 = BigInt(lower), up64 = BigInt(upper);
 
    const mergeSort = (lo, hi) => {
        if (hi - lo <= 1) return 0;
        const mid = (lo + hi) >> 1;
        let count = mergeSort(lo, mid) + mergeSort(mid, hi);
 
        // two-pointer count: for each i in left, find range of j in right satisfying condition
        let jLo = mid, jHi = mid;
        for (let i = lo; i < mid; i++) {
            while (jLo < hi && prefix[jLo] - prefix[i] < lo64) jLo++;
            while (jHi < hi && prefix[jHi] - prefix[i] <= up64) jHi++;
            count += jHi - jLo;                             // valid j count for this i
        }
 
        // merge step: sort the slice in-place
        const merged = prefix.slice(lo, hi).sort((a, b) => a < b ? -1 : a > b ? 1 : 0);
        for (let k = 0; k < merged.length; k++) prefix[lo + k] = merged[k];
        return count;
    };
 
    return mergeSort(0, prefix.length);
};

Complexity: Time O(n log n) — log n merge levels times O(n) merge plus counting. Space O(n) for the prefix array and recursion stack.

Common Mistakes#

1. Forgetting the leading zero in the prefix array. P must start at 0 to capture sums beginning at index 0. Skipping the leading 0 misses every prefix-from-start subarray.
2. Counting after merging. The pair definition relies on i less than j by index. After merging, the original index split is lost. Count first, then merge.
3. Resetting the right pointers per left element. That kills the linear merge guarantee. Both j_lo and j_hi are monotonic across the entire left half.
4. Integer overflow on prefix sums. With nums[i] near INT_MAX and length 10^5, the prefix can exceed 2^31. Use long long in C++, BigInt in JS, or rely on Python's arbitrary precision.
5. Off-by-one in the bound search. j_lo is the smallest j with P[j] - P[i] >= lower; j_hi is the smallest j with P[j] - P[i] > upper. The valid count is j_hi - j_lo. Mixing > and >= silently shifts the answer by one.
6. Compressing only P for the BIT version. You must include both bound expressions (P[j] - upper and P[j] - lower) in the coordinate set so they have ranks to query.

Interview Tips#

• Reformulate to prefix sums up front. The interviewer wants to hear "range sum equals difference of prefix sums" before any algorithm appears. That single observation is the unlock.
• Pick merge sort for clarity. Mention BIT as an alternative; commit to merge sort because the code is shorter and the counting argument is more visual.
• Walk the two-pointer monotonicity. Many candidates write the inner while loops but cannot articulate why both pointers advance only forward. Explaining that earns serious credit.
• Address overflow before coding. "I will use 64-bit arithmetic for prefix sums" is a strong proactive signal.
• Compare to Reverse Pairs and Count Smaller. All three are the same family. Mentioning the family signal that you see the pattern, not just one problem.

Follow-up Questions#

1. Stream version: prefix sums arrive online. Switch to the Fenwick-tree variant since merge sort needs the full array.
2. Find the actual subarrays, not just the count. Memory-augment merge sort to emit pairs; works but uses O(n^2) worst-case space.
3. Range count with multiple windows simultaneously. Use offline processing: sort queries by parameter and reuse one Fenwick tree.
4. 2D variant: count rectangles whose sum is in range. Fix two row boundaries, compute column-prefix sums, apply this 1D algorithm.
5. k-th range sum in [lower, upper]. Augment the Fenwick tree with a k-th order statistic walk.
6. Approximate count under a budget. Use Count-Min Sketch on prefix sums for sublinear memory at the cost of some accuracy.

Key Takeaways#

• Reformulate "subarray sum in range" as "pair of prefix sums whose difference is in range" — this single substitution exposes the divide-and-conquer counting structure.
• Modified merge sort counts pairs across the index split using two monotonic pointers, achieving O(n log n) total work.
• Always count before merging; once merged, the index ordering that defines the pair vanishes.
• Use 64-bit (or BigInt) arithmetic for prefix sums when individual values can be near INT_MAX.
• The Fenwick Tree alternative requires compressing all three quantities (P[i], P[i] - lower, P[i] - upper) into the same coordinate set.
• This template is the same family as Reverse Pairs and Count Smaller — recognize the pattern and reuse the scaffold for any "count pairs satisfying an additive condition" problem.