Command Palette

Search for a command to run...

Hectal
Problem 36.4 · Advanced Data StructuresHard

Count of Range Sum

PatternRange Queries (Fenwick & Segment Trees)Prefix SumDivide and Conquer

What it teaches: Prefix sums turn "subarray sum in [lower, upper]" into counting pairs of prefixes, done with merge sort.

Practise it on judges as “Count of Range Sum”.

In plain words

A subarray's sum equals the difference of two running totals (prefix sums). So the question becomes: how many pairs of prefix sums, earlier and later, differ by an amount between lower and upper? Merge sort the prefix sums; while both halves are sorted, two pointers count the good pairs quickly.

Return how many subarrays have a sum in [lower, upper]. Example: nums = [-2, 5, -1], lower = −2, upper = 2 → 3.

The problem

Count subarrays whose sum lies in [lower, upper] (inclusive).

Example 1

Input: nums = [-2, 5, -1], lower = -2, upper = 2
Output: 3

Constraints

  • 1 ≤ n ≤ 10⁵
  • Sums can exceed int

Pattern clues in the wording

  • → Count subarrays with a sum in a range
  • → Negative numbers (no sliding window)

These clues point to Range Queries (Fenwick & Segment Trees): Answer sums, minimums or counts over any range while the array keeps changing, in O(log n) per query and update.

Stuck? Take one hint at a time

Solution · starter
class Solution {
    public int countRangeSum(int[] nums, int lower, int upper) {
        return 0;
    }
}

Write your solution locally or in your editor for now. Pick Java, Python, C++, JavaScript or Go above: every solution on this page switches with it. The in-browser runner will run these tests right here.

Test cases

#InputExpected
1
nums = [-2,5,-1]
lower = -2
upper = 2
3
2
nums = [0]
lower = 0
upper = 0
1

From slow to fast

Approaches

1. Merge sort on prefix sums · O(n log n)
1

Merge sort on prefix sums

Time O(n log n) Space O(n)

Sort prefixes by merge sort; for each left-half prefix, the matching right-half prefixes form a contiguous window found with two moving pointers.

▶ Dry run: Pairs of prefix sumsnums = [-2, 5, -1], lower = -2, upper = 2
0
p0
-2
p1
3
p2
2
p3

Step 1/4Prefix sums: 0, −2, 3, 2. A subarray sum is p[later] − p[earlier]; it must be between −2 and 2.

Approach 1
class Solution {
    private int lower, upper;

    public int countRangeSum(int[] nums, int lower, int upper) {
        this.lower = lower;
        this.upper = upper;
        long[] prefix = new long[nums.length + 1];
        for (int i = 0; i < nums.length; i++) prefix[i + 1] = prefix[i] + nums[i];
        return sort(prefix, new long[prefix.length], 0, prefix.length - 1);
    }

    private int sort(long[] p, long[] tmp, int lo, int hi) {
        if (lo >= hi) return 0;
        int mid = (lo + hi) >>> 1;
        int count = sort(p, tmp, lo, mid) + sort(p, tmp, mid + 1, hi);
        int a = mid + 1, b = mid + 1;
        for (int i = lo; i <= mid; i++) {
            while (a <= hi && p[a] - p[i] < lower) a++;
            while (b <= hi && p[b] - p[i] <= upper) b++;
            count += b - a;
        }
        int i = lo, j = mid + 1, k = lo;
        while (i <= mid || j <= hi) tmp[k++] = (j > hi || (i <= mid && p[i] <= p[j])) ? p[i++] : p[j++];
        System.arraycopy(tmp, lo, p, lo, hi - lo + 1);
        return count;
    }
}

Verdict: The classic divide-and-conquer count.

Before you submit

Edge cases and common mistakes

Test these inputs

  • Single element
  • All sums out of range

Mistakes people make

  • int prefix sums overflowing.
  • Using a sliding window (fails with negatives).

Interview

Follow-up questions

Fenwick-tree version?