Coordinate Compression

Maps sparse values to dense 0-indexed ranks for use with BIT/segment tree.

[Utilities]|

Jul 9, 2026

|explanatory_notes.md|

#coordinate-compression#discretization#rank

$cat source_code/

cpp

#include <bits/stdc++.h>
using namespace std;

vector<int> coords;

void compressInit() {
    sort(coords.begin(), coords.end());
    coords.erase(unique(coords.begin(), coords.end()), coords.end());
}

int getRank(int x) {
    return lower_bound(coords.begin(), coords.end(), x) - coords.begin();
}

int getValue(int idx) { return coords[idx]; }

int compressSize() { return coords.size(); }

17 linesutf-8

$cat explanation_notes.md

notes_viewer --renderedmarkdown (math enabled)

Coordinate Compression

Transforms a sparse set of values into contiguous ranks $[0, k-1]$ .

How It Works

Collect all values

Sort and deduplicate

Binary search to find rank of any value

When to Use

Values are large but few distinct values exist

Need to index into BIT or segment tree by value

2D geometry problems with large coordinates

Complexity

Init (sort + dedup) —

O(n \log n)

Rank lookup —

O(\log n)

Space —

O(n)