Lesson 36.3 · Advanced Data Structures
Ordered Maps and Coordinate Compression
TreeMap gives sorted keys with floor/ceiling in O(log n). Coordinate compression maps large or negative values to 0..k − 1 so they can index a Fenwick or segment tree.
10 min
Think of it like this
Seating guests by their ticket numbers when the numbers go up to a billion: you sort the tickets and give out seats 1, 2, 3… in that order, keeping the same order with far smaller numbers.
1.Two tools
TreeMap / TreeSet (red-black trees): insert, delete, floor, ceiling, first and last in O(log n). Use them for bookings and intervals that change over time (My Calendar), sliding-window medians, and "closest value" queries.
Coordinate compression: copy the values, sort and deduplicate them, then replace each value with its index (binary search). Counting problems such as "how many smaller elements to the right" then become Fenwick tree queries over 0..k − 1.
Remember
- TreeMap for dynamic sorted keys.
- Compress before indexing a BIT.
- Order is preserved, sizes shrink.
Common mistakes
- Building a Fenwick tree of size 10⁹ instead of compressing.