Coordinate compression

Coordinate compression replaces every value by its place among the distinct values in sorted order: the smallest value becomes 0, the next one 1, and so on. An array indexed by value then needs only as many cells as there are distinct values. Use it when the values are large (up to 10^9, negative, or not integers) but few, say n \le 2 \cdot 10^5, an array indexed by value would help, and only which values are equal or smaller matters.

Explanation

For each of the numbers 2, 5, 2, 0, 3, how many of the numbers are smaller? Count them first: take an array cnt with one cell for every value from 0 to 5 and add 1 to cell x for each number x, so the value itself is the index. The numbers smaller than x are then the counts in the cells to the left of cell x. For 3 that is 1 + 0 + 2 = 3: the 0 and the two 2s.

Fig. 1. Each number adds 1 to the cell with its own number. The numbers smaller than 3 are counted in the cells left of cell 3 (blue).

Real numbers are rarely this small, as in 700, 1000000000, 25, 700, 4000, 25. Counting them the same way needs cells 0 to 10^9, about 4 GB of int, while a typical memory limit is 256 MB, and only 4 of those cells would ever be used.

A natural move is to give each value a small id when it first appears: 700 gets 0, 1000000000 gets 1, 25 gets 2, 4000 gets 3. The array becomes 0, 1, 2, 0, 3, 2, and the counting array needs only 4 cells. But the ids have lost the order. Two values are smaller than 700, the two 25s, yet 700 got id 0, so no cell lies to the left of its cell and the count says none.

So the ids must go up when the values go up. Write the distinct values in increasing order, 25, 700, 4000, 1000000000, and number them by where they stand: 0, 1, 2, 3. This number is the value's place. Equal values get equal places, a smaller value gets a smaller place (25 < 700 and 0 < 1), and there are never more places than elements. Now 700 has place 1, and the cell to its left holds 2, the two 25s. What is lost is the distance: 4000 and 1000000000 are now 2 and 3, right next to each other.

Fig. 2. Numbered as first seen, 25 gets a larger number than 700 (red). Numbered by place, the order is kept (blue).

To get the places, collect the values into a copy, sort it, remove repeats (equal values now stand together), and look up each value's place in the list with binary search.

Fig. 3. Sort, remove repeats, look up: the index of a value in the list of distinct values is its place.

This is coordinate compression, named so because the values are often coordinates of points on a line. The places run from 0 to k - 1, where $k$ is the number of distinct values (here k = 4: places 0 to 3).

In C++

The template turns the array a of n values into the array c of their places. vals is the sorted list of distinct values, and its index is the place.

vector<int> c(n);
// collect
vector<int> vals = a;
// sort
sort(vals.begin(), vals.end());
// remove repeats
vals.erase(unique(vals.begin(), vals.end()), vals.end());
// look up
for (int i = 0; i < n; i++)
    c[i] = lower_bound(vals.begin(), vals.end(), a[i]) - vals.begin();
// now vals[c[i]] == a[i], and there are k = vals.size() places

On a sorted vector, unique moves the first value of each block of equal values to the front and returns where that part ends; the vector keeps its size, with leftovers behind, and erase cuts them off. lower_bound minus vals.begin() is the index of the value in vals. For long long or double values, change the element type of a and vals.

One sort and $n$ binary searches take O(n \log n) time, and anything indexed by place needs only k \le n cells (4 instead of 10^9 + 1 for the six numbers above).

Counting smaller values

A counting array over places has vals.size() cells. To find how many values are smaller than each element, count each place, then add up the counts from the left: smaller[r] is the sum of the counts at places below r. On 700, 1000000000, 25, 700, 4000, 25 this prints 2, 5, 0, 2, 4, 0.

vector<int> cnt(vals.size(), 0);
for (int i = 0; i < n; i++)
    cnt[c[i]]++;
vector<int> smaller(vals.size(), 0);     // values with a place below r
for (int r = 1; r < (int)vals.size(); r++)
    smaller[r] = smaller[r - 1] + cnt[r - 1];
for (int i = 0; i < n; i++)
    cout << smaller[c[i]] << ' ';

Segments and points

Given segments [l, r] and points with coordinates up to 10^9, count for each point how many segments contain it. A difference array over places does it: add 1 at the place where a segment starts and subtract 1 just after the place where it ends, so a running total from the left counts the segments open at each place.

Take segments $[100,300]$, $[200,600]$, $[400,600]$ and points 350, 50, 600. The points go into vals together with the segment ends, and the answers for 350, 50 and 600 are 1, 0 and 2.

Fig. 4. Each segment adds 1 at its start and subtracts 1 after its end (row d); the running total gives the cover counts. Point 350 (blue) has a place of its own, with cover count 1.

If the points were left out, vals would be 100, 200, 300, 400, 600 with cover counts 1, 2, 2, 2, 2. Point 350 has no place of its own, so lower_bound gives it the place of 400 and the answer 2. Point 50 gets the place of 100 and the answer 1 instead of 0, and a point beyond 600 gets place vals.size(), outside the array. That is why every value the program will look up goes into vals before the sort.

// look up: the place of x in vals
int place(const vector<int>& vals, int x) {
    return lower_bound(vals.begin(), vals.end(), x) - vals.begin();
}

// collect: segment ends and points together
vector<int> vals;
for (int i = 0; i < n; i++) {
    vals.push_back(l[i]);
    vals.push_back(r[i]);
}
for (int j = 0; j < m; j++)
    vals.push_back(p[j]);
// sort, remove repeats
sort(vals.begin(), vals.end());
vals.erase(unique(vals.begin(), vals.end()), vals.end());

int k = vals.size();
vector<int> d(k + 1, 0);                 // k + 1 cells: place of r plus 1 can be k
for (int i = 0; i < n; i++) {
    d[place(vals, l[i])]++;
    d[place(vals, r[i]) + 1]--;
}
vector<int> cover(k);
int run = 0;
for (int t = 0; t < k; t++) {
    run += d[t];
    cover[t] = run;
}
for (int j = 0; j < m; j++)
    cout << cover[place(vals, p[j])] << ' ';

With $n$ segments and $m$ points there are k \le 2n + m places, and the whole thing takes O((n + m) \log(n + m)) time.

Common mistakes

• Calling unique without erase. On 10, 10, 30, 50, 50 the size stays 5 instead of 3, so k and every array sized by it are wrong. Write vals.erase(unique(vals.begin(), vals.end()), vals.end()).

• Measuring lengths in places. Segments $[0,10]$ and $[1000,1010]$ cover a length of 20, but their places 0, 1, 2, 3 give 1 + 1 = 2. The length between places r and r + 1 is vals[r + 1] - vals[r].

Similar techniques

Binary search on the sorted values counts the values in a range $[x,y]$ with upper_bound - lower_bound, no compression needed.

A map counts large values directly, at O(\log n) per access. Compress when the next step needs an array with indexes 0 to k - 1.

Difference arrays, prefix sums, the Fenwick tree and the segment tree all need small indexes, so with values up to 10^9 they run over places after compression.

Counting sort needs small values; when only the order matters, compression makes them small.

Practice