Count of Range Sum

Hard· Fenwick tree· prefix sums

Problem

Given an integer array and bounds lower and upper, count the contiguous subarrays whose sum lies within [lower, upper] inclusive. The array is too long to enumerate all subarrays.

Examples

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

Output: 3

Subarrays [0,0], [2,2] and [0,2].

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

Output: 1

Constraints

• 1 <= nums.length <= 10^5
• -2^31 <= nums[i] <= 2^31 - 1
• -10^5 <= lower <= upper <= 10^5

Hints & approach

Hint 1

Rewrite subarray sums as differences of prefix sums P[j] - P[i].

Hint 2

For each j, count earlier prefixes P[i] in [P[j] - upper, P[j] - lower].

Hint 3

Compress all prefix sums and use a Fenwick tree for range counts.

Approachtry the hints first

Compute prefix sums P[0..n] with P[0] = 0 in 64-bit integers, and compress them to sorted ranks. Iterate j from 0 to n: binary-search the rank range whose values fall in [P[j] - upper, P[j] - lower], add the Fenwick count of already-inserted prefixes in that range, then insert P[j]. Merge sort on the prefix array with two moving pointers is an alternative with the same complexity.

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

← PreviousReverse Pairs DoneBack to Segment tree / Fenwick