Coordinate Compression

You have coordinates, timestamps, or array values in 1..1e9, but only n ≤ 2e5 of them actually appear. A Fenwick tree, a segment tree, or a dense boolean array wants an index in 0..k-1, not a hole-ridden 1e9 universe.

Coordinate compression is the rename: replace every value x with its rank among the distinct values. Order is preserved. Distances are not — ranks are adjacent even if the originals were 2 and 10^9.

Sort unique, then lower_bound for the rankjs

function uniqueSorted(a) {
  return [...new Set(a)].sort((x, y) => x - y);
}

// first index i with uniq[i] >= x, assuming uniq is sorted
function lowerBound(uniq, x) {
  let lo = 0;
  let hi = uniq.length;
  while (lo < hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (uniq[mid] < x) lo = mid + 1;
    else hi = mid;
  }
  return lo;
}

function compress(a) {
  const uniq = uniqueSorted(a);
  return a.map((x) => lowerBound(uniq, x));
}

TRACE

a = [100, 5, 100, 40]. Build ranks 0..k-1, then rewrite a.

Collect

The raw values. Duplicates are allowed in a; they will share a rank.

0100

2100

340

k will be the number of distinct values

1 / 4

In C++ the same two lines are sort(all(v)); v.erase(unique(all(v)), v.end()); then int id = lower_bound(all(v), x) - v.begin();. A hash map from value → rank also works if you only look up values that exist. Query endpoints that might fall between keys still need lower_bound (first rank ≥ L, first rank > R) so a range on the original line maps onto a dense segment.

A hash map alone does not give you 'the next key after L'. Sorting does.

CHECK

You need a Fenwick tree for point updates at coordinates x, with 1 ≤ x ≤ 1e9 and at most 2e5 distinct x. Why compress?

CHECK

uniq = [2, 7, 9] after sort-unique. A range query asks for original coordinates [3, 8]. Which ranks cover every stored key in that range?

CHECK

After compression, two original values 10 and 1e9 become ranks 3 and 4. What is still true?

Checks 0/3

Next lesson