Coordinate Compression

Replace values from a huge range with their ranks in the set of values that actually occur. A $10^9$-sized dimension becomes $O(n)$, which is what makes array-based data structures applicable.

The idiom

vector<long long> vals = a;                       // all values that matter
sort(vals.begin(), vals.end());
vals.erase(unique(vals.begin(), vals.end()), vals.end());
 
auto id = [&](long long x) {
    return lower_bound(vals.begin(), vals.end(), x) - vals.begin();
};
for (auto& x : a) x = id(x);                      // now in [0, m)

$O(n\log n)$, and vals[i] recovers the original value.

Collect every value that will ever be queried, not just the ones in the array — query endpoints, thresholds, and derived values all need to be in vals.

When you need it

Situation	Why
Values up to $10^9$, need a BIT/segment tree over values	array size must be $O(n)$
Counting inversions	BIT indexed by value
Sweep line with $y$ up to $10^9$	segment tree over compressed $y$
$k$-th smallest in a range	persistent segment tree over values
Grid problems with sparse coordinates	compress rows and columns independently
DP indexed by value	the state space shrinks to $O(n)$
Offline queries with arbitrary keys	map keys to $[0,m)$

Compressing intervals — the +1 trap

Endpoints are not enough for intervals

When compressing intervals $[l,r]$, the gaps between consecutive values can matter. Compressing only the endpoints merges distinct empty regions.

Standard fixes:

1. Insert $l$, $r$ and $r+1$ for every interval, then work with half-open intervals $[l,r+1)$.
2. Or store, alongside each compressed index, the length of the real-world span it represents, and weight sums by that length.

The second is what a rectangle-union sweep does: the segment tree is indexed by compressed $y$, but each leaf’s contribution is ys[i+1] - ys[i], not 1.

Alternatives

Alternative	When
map<long long, T>	few distinct values, code simplicity matters more than speed
Dynamic (sparse) segment tree	values arrive online, cannot be collected first
Persistent segment tree over the value range	online queries, implicit nodes
Hash map	no ordering needed
Sort + binary search	exactly the compression above

Dynamic segment trees are the right choice when the queries are online and you genuinely cannot see all coordinates up front. Otherwise compression is faster and uses less memory.

Compressing more than numbers

The technique is “map arbitrary keys to a dense integer range”, so it applies to:

• strings — sort and rank, or use a map<string,int>;
• pairs — sort the distinct pairs;
• graph vertices given by arbitrary labels;
• time points in an offline sweep;
• states in a DP over a sparse state space.

Multi-dimensional compression

Compress each axis independently:

compress(xs); compress(ys);
// grid is now m_x by m_y, with m_x, m_y <= 2n

For a rectangle-union area, the compressed grid has $O(n^2)$ cells — fine for $n\le 2000$, but for larger $n$ use a sweep line over one axis and a segment tree over the other, which is $O(n\log n)$.

A worked example: counting inversions

compress(a);                                       // values now in [0, n)
BIT bit(n);
long long inv = 0;
for (int i = n - 1; i >= 0; i--) {
    inv += bit.query(a[i] - 1);                    // already-seen values smaller than a[i]
    bit.update(a[i], 1);
}

Without compression the BIT would need $10^9$ entries; with it, $n$. This pairing — compress, then index a BIT by value — is one of the most reused combinations in competitive programming.

See also: Fenwick Tree · Sweep Line · Persistent Structures