Coordinate Compression
Replace large or sparse values by their rank order so array-based structures become practical again.
Coordinate Compression
The main note is rendered from the TeX source. Code lives in a separate C++ file so the write-up stays readable.
Overview
Coordinate compression is not an optimization trick in isolation. It is the preprocessing step that makes an array-based solution legal once the original values are too large, negative, or sparse.
Problem-Driven Motivation
Suppose an array contains values up to \(10^9\), possibly negative, and the intended solution is:
Fenwick tree over value ranks,
segment tree over event coordinates,
frequency array over distinct values.
The algorithmic idea is fine, but allocating arrays indexed directly by raw coordinates is impossible. What really matters is usually not the exact coordinate size. It is the relative order.
That is exactly the situation where compression turns a dead idea into a working one.
Recognition Pattern
Compression is usually the right move when:
values are huge but only \(O(n)\) of them ever appear,
comparisons such as \(<\), \(\le\), or equality are the only important operations,
the next structure wants small integer indices,
the full set of referenced values is known offline.
Typical contest phrases are: ``values up to \(10^9\)'', ``negative coordinates'', ``sparse points'', and ``after sorting, the actual distances do not matter.''
Derivation
If an algorithm only depends on order, then replacing every value by its rank does not change the answer.
Formally, after sorting the distinct values \[ v_0 < v_1 < \cdots < v_{k-1}, \] map every original value \(x\) to the unique index \(id(x)\) such that \(v_{id(x)} = x\).
Then:
\(x < y \iff id(x) < id(y)\),
\(x = y \iff id(x) = id(y)\).
That is enough for rank-based data structures.
What compression does not preserve is geometric length. If an interval length or coordinate gap matters directly, you must either keep the original values too, or transform the problem more carefully.
Worked Problem
Problem.
Count inversions in an array of length \(n \le 2 \cdot 10^5\), where values may be negative and as large as \(10^9\).
Why the naive approach fails.
The naive double loop is \(O(n^2)\). A Fenwick tree over raw values is impossible because the value range is far too large.
How compression fixes it.
Collect all array values.
Sort and deduplicate them.
Replace each value by its rank.
Process the array from left to right with a Fenwick tree over compressed ranks.
If the current value has compressed rank \(r\), then the number of earlier elements greater than it is: \[ \texttt{seen\_so\_far} - \texttt{fenwick.prefix\_sum}(r+1). \]
Why this is correct.
Compression preserves the order ``greater than'' exactly. So counting bigger ranks is the same as counting bigger original values.
Implementation Reasoning
The practical questions that matter are:
When do I collect values? Before building the mapping, gather every value that any later operation will reference. In offline problems this includes query values, endpoints, and sometimes transformed values like \(r+1\).
Do I need reverse mapping? Keep the sorted unique array if later logic needs the original values back.
0-index or 1-index? Compression itself is naturally 0-indexed, but Fenwick trees are often 1-indexed. Convert once and keep it consistent.
The code below provides a reusable compressor plus an inversion-counting application.
Correctness Intuition
Compression only changes labels. It does not change the sorted order of equal or distinct values. Therefore any algorithm whose logic depends solely on order or equality behaves identically after remapping.
Complexity Analysis
For \(m\) collected values:
build compression: \(O(m \log m)\),
one lookup with
lower_bound: \(O(\log m)\),memory: \(O(m)\).
Common Pitfalls
Forgetting to include values that appear only in future queries.
Compressing interval endpoints but forgetting that a half-open model may also need \(r+1\).
Treating compressed indices as if their differences were real geometric distances.
Mixing 0-indexed compressed values with a 1-indexed Fenwick tree.
Variants and Failure Modes
Compress pairs or tuples lexicographically when one scalar is not enough.
Compress both axes in offline geometry or rectangle-query problems.
If updates introduce previously unseen coordinates online, static compression is no longer enough; use maps, balanced trees, or rebuild offline.
Practice Problems
Inversion counting.
Offline rectangle counting after compressing one or two axes.
Dynamic frequency or order-statistics queries on large sparse values.
References
Code
Contest-ready reference implementation for the idea explained above.
#include <bits/stdc++.h>
using namespace std;
template <class T>
struct CoordinateCompression {
vector<T> values;
void add_value(const T& x) {
values.push_back(x);
}
void build() {
sort(values.begin(), values.end());
values.erase(unique(values.begin(), values.end()), values.end());
}
int index(const T& x) const {
return (int)(lower_bound(values.begin(), values.end(), x) - values.begin());
}
T value_at(int idx) const {
return values[idx];
}
int size() const {
return (int)values.size();
}
};
struct Fenwick {
int n;
vector<long long> bit;
explicit Fenwick(int n) : n(n), bit(n + 1, 0) {}
void add(int idx, long long delta) {
for (; idx <= n; idx += idx & -idx) bit[idx] += delta;
}
long long prefix_sum(int idx) const {
long long result = 0;
for (; idx > 0; idx -= idx & -idx) result += bit[idx];
return result;
}
};
template <class T>
vector<int> compress_vector(const vector<T>& a, vector<T>* sorted_unique = nullptr) {
CoordinateCompression<T> cc;
for (const T& x : a) cc.add_value(x);
cc.build();
vector<int> compressed;
compressed.reserve(a.size());
for (const T& x : a) compressed.push_back(cc.index(x));
if (sorted_unique) *sorted_unique = cc.values;
return compressed;
}
// Example application: count inversions in an array with large or negative values.
long long count_inversions_with_compression(const vector<long long>& a) {
vector<int> compressed = compress_vector(a);
int max_rank = 0;
for (int x : compressed) max_rank = max(max_rank, x);
Fenwick fw(max_rank + 1);
long long inversions = 0;
for (int i = 0; i < (int)compressed.size(); ++i) {
int rank = compressed[i] + 1; // Fenwick is 1-indexed.
long long not_greater = fw.prefix_sum(rank);
inversions += i - not_greater;
fw.add(rank, 1);
}
return inversions;
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.