Pattern Guide
Coordinate Compression
"Map large values to small ranks. Enables Fenwick/SegTree on value-based problems."
Coordinate compression maps a set of large values (up to 10^9) to small ranks (1..n) without changing relative order. This allows using data structures like Fenwick Trees and Segment Trees on problems where values span a huge range. Prerequisite for many hard problems involving counting inversions, LIS with Fenwick, and 2D range queries.
Problems you can solve with this pattern
4 problems · click any to start solving
// Given values that can be up to 10^9, compress to ranks 1..n
function compress(values) {
// Step 1: collect all unique values
const unique = [...new Set(values)].sort((a,b) => a-b);
// Step 2: build rank map
const rank = new Map(unique.map((v,i) => [v, i+1])); // 1-indexed
// Step 3: replace values with ranks
return { ranks: values.map(v => rank.get(v)), n: unique.length, rank, unique };
}
// Lower bound: rank of x = first rank with unique[rank-1] >= x
// Used for: "count elements less than x" = query(lowerBound(x) - 1)
// Example: values = [100, 50, 200, 50, 100]
// unique = [50, 100, 200] → ranks: [2, 1, 3, 1, 2]
// Fenwick tree of size 3 instead of 200!
// Combined with Fenwick tree for counting/inversions:
function countInversions(nums) {
const unique = [...new Set(nums)].sort((a,b)=>a-b);
const rank = new Map(unique.map((v,i)=>[v,i+1]));
const n = unique.length;
const bit = new Array(n+1).fill(0);
const update = i => { for(;i<=n;i+=i&(-i)) bit[i]++; };
const query = i => { let s=0; for(;i>0;i-=i&(-i)) s+=bit[i]; return s; };
let inversions = 0;
for(const x of nums) {
const r = rank.get(x);
inversions += query(n) - query(r); // count elements already inserted that are > x
update(r);
}
return inversions;
}Coordinate compression solves the "values are too large for array indexing" problem. If you need a Fenwick tree on values up to 10^9, you can't allocate 10^9 slots. Instead: collect all values that appear, sort them, and replace each value with its rank (1..n). The relative order is preserved — that's all you need for count-based queries.
The Technique
// Given values that can be up to 10^9, compress to ranks 1..n
function compress(values) {
// Step 1: collect all unique values
const unique = [...new Set(values)].sort((a,b) => a-b);
// Step 2: build rank map
const rank = new Map(unique.map((v,i) => [v, i+1])); // 1-indexed
// Step 3: replace values with ranks
return { ranks: values.map(v => rank.get(v)), n: unique.length, rank, unique };
}
// Lower bound: rank of x = first rank with unique[rank-1] >= x
// Used for: "count elements less than x" = query(lowerBound(x) - 1)
// Example: values = [100, 50, 200, 50, 100]
// unique = [50, 100, 200] → ranks: [2, 1, 3, 1, 2]
// Fenwick tree of size 3 instead of 200!
// Combined with Fenwick tree for counting/inversions:
function countInversions(nums) {
const unique = [...new Set(nums)].sort((a,b)=>a-b);
const rank = new Map(unique.map((v,i)=>[v,i+1]));
const n = unique.length;
const bit = new Array(n+1).fill(0);
const update = i => { for(;i<=n;i+=i&(-i)) bit[i]++; };
const query = i => { let s=0; for(;i>0;i-=i&(-i)) s+=bit[i]; return s; };
let inversions = 0;
for(const x of nums) {
const r = rank.get(x);
inversions += query(n) - query(r); // count elements already inserted that are > x
update(r);
}
return inversions;
}- Values up to 10^9 but only n ≤ 10^5 distinct values appear
- Need a Fenwick/Segment tree indexed by VALUE (not position)
- Counting/querying by value range: how many elements ≤ x
Template: collect all values, sort, deduplicate, map each → rank. Then use ranks as array indices.
Offline vs online: Coordinate compression requires knowing all values upfront (offline). For online queries (values arrive one by one), use a balanced BST or dynamic segment tree instead.