Coordinate Compression

When interval endpoints span $[0, 10^9]$ but there are only $n$ intervals, compress coordinates.

function compress(intervals)
    // Collect all endpoints
    points := set()
    for interval in intervals
        points.add(interval.low)
        points.add(interval.high)

    // Sort and map to compressed indices
    sorted := sort(points)
    compress := map from value to index
    for i from 0 to length(sorted) - 1
        compress[sorted[i]] := i

    // Convert intervals to compressed form
    for interval in intervals
        interval.low := compress[interval.low]
        interval.high := compress[interval.high]

Now the range is $[0, 2n)$ instead of $[0, 10^9]$. Build segment tree on this compressed range.

Time: $O(n \log n)$ for compression. Space: $O(n)$.