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: $O(n \log n)$. Space: $O(n)$.