Implementation steps:
Build prefix sum array
Collect all values: prefix sums, prefix - lower, prefix - upper
Coordinate compress to indices to
Build segment tree for counting
For each prefix sum (left to right): - Query count in compressed range - Add prefix sum position to tree # Query: count of values in [lo, hi] # Update: add 1 at position idx The segment tree tracks counts. Query returns how many prefix sums (added so far) fall in the target range. This problem combines multiple techniques: prefix sums, coordinate compression, and segment trees. Time: . Space: .