#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/data-structures/interval-trees/coordinate-compression

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/data-structures/interval-trees/coordinate-compression

Repovive

Coordinate Compression - Interval Trees | Data Structures | Repovive

Repovive.

Data Structures19 sections · 729 units49h total

Open in Course

Coordinate Compression

Handling large ranges

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