#327
Count of Range Sum
Hard Fenwick tree over compressed prefix sums
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Count subarrays whose sum lies within [lower, upper].
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: count subarrays with sum in [lower, upper].
Why this works: with prefix sums, count earlier prefixes in [P - upper, P - lower] for each P. Compress the values and count with a Fenwick tree.
Example: [-2, 5, -1], range [-2, 2]
valid: [-2], [-1], [-2, 5, -1] → 3✦Hints open one at a time
With prefix sums P, a subarray (i, j] is valid when lower ≤ P[j] − P[i] ≤ upper.
For each j, count earlier prefixes P[i] in [P[j] − upper, P[j] − lower].
Coordinate-compress all prefix sums and count them with a Fenwick tree.
↗Approach
Compute long prefix sums, sort the distinct values, and for each P[j] in order: query how many earlier prefixes fall in the window (two binary searches + two BIT prefix queries), then add P[j] to the BIT.
</>Solution (Java)
import java.util.*;
class Solution {
private int[] tree;
public int countRangeSum(int[] nums, int lower, int upper) {
int n = nums.length;
long[] pre = new long[n + 1];
for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + nums[i];
long[] sorted = Arrays.stream(pre).distinct().sorted().toArray();
tree = new int[sorted.length + 1];
int count = 0;
for (long p : pre) {
int hi = upperIndex(sorted, p - lower); // values <= p - lower
int lo = upperIndex(sorted, p - upper - 1); // values <= p - upper - 1
count += query(hi) - query(lo);
add(Arrays.binarySearch(sorted, p) + 1);
}
return count;
}
// number of sorted values <= x
private int upperIndex(long[] a, long x) {
int lo = 0, hi = a.length;
while (lo < hi) {
int mid = (lo + hi) >>> 1;
if (a[mid] <= x) lo = mid + 1;
else hi = mid;
}
return lo;
}
private void add(int i) {
for (; i < tree.length; i += i & -i) tree[i]++;
}
private int query(int i) {
int s = 0;
for (; i > 0; i -= i & -i) s += tree[i];
return s;
}
}!Common mistake
Using int prefix sums — they overflow with values near 2^31.
Complexity
- Time: O(n log n).
- Space: O(n).
Topic: Segment Tree, Fenwick & Sparse Table
🎬 Episodes 98–100: video coming soon