Data Structures19 sections · 729 units
Open in Course

Count Range Sum Solution

Implement your solution

Implementation steps:

1.1. Build prefix sum array

2.2. Collect all values: prefix sums, prefix - lower, prefix - upper

3.3. Coordinate compress to indices 00 to m−1m-1

4.4. Build segment tree for counting

5.5. 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)$.