Count of Range Sum
Problem
Return the number of subarrays whose sum lies in [lower, upper]. Use prefix sums P so that S(i, j) = P[j+1] − P[i]; count pairs (i, j) with lower ≤ P[j] − P[i] ≤ upper.
nums = [-2, 5, -1], lower = -2, upper = 23def count_range_sum(nums, lower, upper):
pre = [0]
for x in nums: pre.append(pre[-1] + x)
def merge_count(l, r):
if r - l <= 1: return 0
m = (l + r) // 2
cnt = merge_count(l, m) + merge_count(m, r)
j = k = m
for i in range(l, m):
while j < r and pre[j] - pre[i] < lower: j += 1
while k < r and pre[k] - pre[i] <= upper: k += 1
cnt += k - j
pre[l:r] = sorted(pre[l:r])
return cnt
return merge_count(0, len(pre))function countRangeSum(nums, lower, upper) {
const pre = [0];
for (const x of nums) pre.push(pre[pre.length - 1] + x);
function mergeCount(l, r) {
if (r - l <= 1) return 0;
const m = (l + r) >> 1;
let cnt = mergeCount(l, m) + mergeCount(m, r);
let j = m, k = m;
for (let i = l; i < m; i++) {
while (j < r && pre[j] - pre[i] < lower) j++;
while (k < r && pre[k] - pre[i] <= upper) k++;
cnt += k - j;
}
const part = pre.slice(l, r).sort((a, b) => a - b);
for (let i = 0; i < part.length; i++) pre[l + i] = part[i];
return cnt;
}
return mergeCount(0, pre.length);
}class Solution {
long[] pre; int lo, hi;
public int countRangeSum(int[] nums, int lower, int upper) {
pre = new long[nums.length + 1];
for (int i = 0; i < nums.length; i++) pre[i + 1] = pre[i] + nums[i];
lo = lower; hi = upper;
return merge(0, pre.length);
}
int merge(int l, int r) {
if (r - l <= 1) return 0;
int m = (l + r) / 2;
int cnt = merge(l, m) + merge(m, r);
int j = m, k = m;
for (int i = l; i < m; i++) {
while (j < r && pre[j] - pre[i] < lo) j++;
while (k < r && pre[k] - pre[i] <= hi) k++;
cnt += k - j;
}
long[] part = Arrays.copyOfRange(pre, l, r);
Arrays.sort(part);
System.arraycopy(part, 0, pre, l, part.length);
return cnt;
}
}vector<long> pre; int lo, hi;
int merge_(int l, int r) {
if (r - l <= 1) return 0;
int m = (l + r) / 2;
int cnt = merge_(l, m) + merge_(m, r);
int j = m, k = m;
for (int i = l; i < m; i++) {
while (j < r && pre[j] - pre[i] < lo) j++;
while (k < r && pre[k] - pre[i] <= hi) k++;
cnt += k - j;
}
sort(pre.begin() + l, pre.begin() + r);
return cnt;
}
int countRangeSum(vector<int>& nums, int lower, int upper) {
pre.assign(nums.size() + 1, 0);
for (int i = 0; i < (int)nums.size(); i++) pre[i + 1] = pre[i] + nums[i];
lo = lower; hi = upper;
return merge_(0, pre.size());
}Explanation
Any subarray sum can be written with prefix sums: the sum of nums[i…j] equals P[j+1] - P[i]. So counting subarrays with sum in [lower, upper] becomes counting pairs i < j where lower <= P[j] - P[i] <= upper.
Checking all pairs is O(n²). The faster idea is a modified merge sort on the prefix array pre. Each recursive call sorts a half, and while combining the two sorted halves we count the valid cross-pairs cheaply.
For each left index i, we slide two pointers j and k over the right half. j moves to the first spot where pre[j] - pre[i] >= lower, and k moves past the last spot where pre[k] - pre[i] <= upper. Then k - j is exactly how many right-side prefixes pair validly with pre[i].
Because both halves are sorted, those pointers only move forward and never reset, so each merge level is linear. After counting, we sort the slice (pre[l:r] = sorted(...)) so the parent merge sees sorted data. Overall this is O(n log n).
Example: nums = [-2, 5, -1], range [-2, 2]. The valid subarrays are [-2], [-1], and the whole [-2, 5, -1] (sum 2), giving an answer of 3.