Count of Range Sum
Solve and submit on LeetCode to build your LeetCode profile. Use the hints here when you need guidance.
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
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)
