Coordinate compression with a segment tree

Why this matters

The earlier lessons in this module used array positions as the keys of the tree. Position 0 is the first slot, position 1 is the second, and so on. Many real problems store values instead of positions. A value can be a price, a timestamp or a score. It can be as large as 1,000,000,000.

A segment tree over those raw values would need about a billion slots. That is about 4 GB of memory for 4-byte numbers, and almost all of the slots would stay empty.

Coordinate compression solves this problem. It maps the values that really appear in the input to the small numbers 0, 1, 2 and so on. The order of the values is kept. Then the segment tree works on those small numbers.

This lesson builds the method step by step. It uses the point-update and range-sum tree from the building lesson. It does not explain that tree again. The merge sort tree in the next lesson answers a different kind of question on the same kind of input.

A concrete problem

A shop records the price of each item it sells. The shop sends the program a list of lines. Two kinds of lines can appear.

• add x records one item with price x.
• count lo hi asks how many recorded items have a price from lo to hi. Both ends are included.

Here is an example input.

add 900000000
add 5
count 1 100
add 42
count 1 1000000000
count 40 50
count 6 41

The first count asks for prices from 1 to 100. Only the item with price 5 is in that range, so the answer is 1. The second count covers every price, so it sees three items and the answer is 3.

The program must answer each count quickly, without looking at every recorded item. It must also handle prices as large as a billion. The rest of this lesson shows how.

Why one slot per value fails

A first idea is to give every possible price its own slot. Slot 5 would hold the number of items that cost 5. A count query would then be a range sum over slots, and the segment tree can do that.

The problem is the size. Prices go up to 1,000,000,000, so the array needs more than a billion slots before any item is stored. Most of them would stay at zero.

The fix rests on one observation. Only the prices that appear in the input matter. In the example there are three of them: 5, 42 and 900000000. The number of distinct prices is never more than the number of add lines, so the tree can be sized by that number instead.

The idea: rank instead of value

The rank of a value is its position in the sorted list of distinct values. Counting starts at 0. To get the list, sort the stored values and remove repeats. The index of each value in that list is its rank.

For the example, the list and the ranks look like this.

sorted distinct values:  5    42    900000000
rank (index in list):    0    1     2

Ranks keep the order of the values. If one value is smaller than another, its rank is smaller too. This is the one property the tree needs.

The price range 1 to 100 contains 5 and 42, but not 900000000. In rank terms, that range is ranks 0 to 1. The segment tree can answer questions about a range of ranks in the usual way.

This step is called coordinate compression. The prices are points on a number line, which mathematicians call coordinates. Compression squeezes those points into a short line of ranks.

Turning a price range into a rank range

A query bound does not have to be a stored value. The query 1 to 100 uses 1 and 100, and neither one is in the list. The program needs two things: the first rank whose value is at least lo, and the first rank whose value is above hi. Those two positions are the start and the end of the rank range.

The C++ standard library has two functions for this on a sorted list. Both are in the <algorithm> header.

• std::lower_bound(first, last, x) returns the position of the first value that is greater than or equal to x.
• std::upper_bound(first, last, x) returns the position of the first value that is strictly greater than x.

Both functions return an iterator, which is a position marker into the list. Subtracting sorted.begin() turns the marker into a plain index.

Take the sorted list 5, 42, 900000000 again. For the query 1 to 100:

• lower_bound for 1 returns index 0, because 5 is the first value that is at least 1.
• upper_bound for 100 returns index 2, because 900000000 is the first value above 100.

The ranks from index 0 up to index 2 are the answer. Index 2 is not included. This is a half-open range. It includes the start and excludes the end. Its length is end minus start. The range has ranks 0 and 1, which hold the values 5 and 42.

If start equals end, the range is empty. That happens for the query 6 to 41. lower_bound for 6 returns index 1, because 42 is the first value that is at least 6. upper_bound for 41 also returns index 1, because 42 is the first value above 41. The range is empty, so the answer is 0.

The tree over ranks

The tree has one slot for each rank. Adding an item means adding 1 to the slot of its rank. A count query means summing a range of slots.

The class below is a sum tree. Its add function changes one slot and its sum function adds up a range. Both are recursive, which means each function calls itself on the left half or the right half of its range, as the building lesson showed. The tree keeps its numbers in a std::vector of size 4n, where n is the number of slots. That size is large enough for any tree over n slots.

The full program is in the first worked example below.

Worked example 1: the full program

This program reads all the lines first. It then builds the sorted list and answers each line in input order.

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
 
// A segment tree over ranks 0..n-1. It supports adding to one slot and
// summing a range of slots.
class SumTree {
public:
    explicit SumTree(int n) : n_(n), t_(4 * static_cast<std::size_t>(n), 0) {}
 
    void add(int pos, long long delta) { addRec(1, 0, n_ - 1, pos, delta); }
 
    // Sum of slots l..r, both ends included.
    long long sum(int l, int r) const { return sumRec(1, 0, n_ - 1, l, r); }
 
private:
    int n_;
    std::vector<long long> t_;
 
    void addRec(int node, int lo, int hi, int pos, long long delta) {
        if (lo == hi) {
            t_[node] += delta;
            return;
        }
        int mid = (lo + hi) / 2;
        if (pos <= mid) {
            addRec(2 * node, lo, mid, pos, delta);
        } else {
            addRec(2 * node + 1, mid + 1, hi, pos, delta);
        }
        t_[node] = t_[2 * node] + t_[2 * node + 1];
    }
 
    long long sumRec(int node, int lo, int hi, int l, int r) const {
        if (r < lo || hi < l) return 0;
        if (l <= lo && hi <= r) return t_[node];
        int mid = (lo + hi) / 2;
        return sumRec(2 * node, lo, mid, l, r) + sumRec(2 * node + 1, mid + 1, hi, l, r);
    }
};
 
struct Op {
    std::string kind;  // "add" or "count"
    long long a = 0;   // the value for "add", or lo for "count"
    long long b = 0;   // hi for "count"
};
 
int main() {
    std::vector<Op> ops;
    std::string kind;
    while (std::cin >> kind) {
        Op op{kind};
        if (kind == "add") {
            std::cin >> op.a;
        } else {
            std::cin >> op.a >> op.b;
        }
        ops.push_back(op);
    }
 
    // Step 1: collect every value that will be stored, sorted, without repeats.
    std::vector<long long> sorted;
    for (const Op& op : ops) {
        if (op.kind == "add") sorted.push_back(op.a);
    }
    std::sort(sorted.begin(), sorted.end());
    sorted.erase(std::unique(sorted.begin(), sorted.end()), sorted.end());
 
    // Step 2: answer the operations in input order.
    SumTree tree(static_cast<int>(sorted.size()));
    for (const Op& op : ops) {
        if (op.kind == "add") {
            int rank = static_cast<int>(std::lower_bound(sorted.begin(), sorted.end(), op.a) - sorted.begin());
            tree.add(rank, 1);
        } else {
            // Ranks of stored values in [lo, hi] form the half-open range [first, last).
            int first = static_cast<int>(std::lower_bound(sorted.begin(), sorted.end(), op.a) - sorted.begin());
            int last = static_cast<int>(std::upper_bound(sorted.begin(), sorted.end(), op.b) - sorted.begin());
            long long answer = (first < last) ? tree.sum(first, last - 1) : 0;
            std::cout << answer << '\n';
        }
    }
}

The compiler accepts the program with no warnings:

$ g++ -std=c++20 -Wall -o compress compress.cpp
$ ./compress < input1.txt
1
3
1
0

Here is what each step does. The loop that reads the input stores every line in ops. The first for loop copies the prices from the add lines into sorted. Then sort puts them in order, and unique with erase removes repeats. The sorted list has three values, so the tree has three slots.

The second loop handles the lines in order. An add line finds its rank with lower_bound and adds 1 to that slot. A count line finds its rank range with two bound functions and sums that range.

Read the four outputs against the input. The first count sees the items 900000000 and 5. Only 5 is in range 1 to 100, so the answer is 1. The second count sees all three items, so the answer is 3. The third count, for prices 40 to 50, finds only 42, so the answer is 1. The last count, for 6 to 41, finds nothing, so the answer is 0.

Worked example 2: negatives and repeated values

The second example is harder for two reasons. Some prices are negative, and some prices repeat. Repeats are common in real data. Two shops can both sell an item for the same price.

add -3
add 10
add -3
add 7
count -5 0
count -3 7
count 8 1000
count -100 -4

Run the same program on this input.

$ ./compress < input2.txt
2
3
1
0

The sorted distinct list is -3, 7, 10. The ranks are 0, 1 and 2. The price -3 appears twice, but it has only one rank. Both copies add 1 to the same slot, so slot 0 ends up holding 2.

Now check each count by hand.

• Count -5 to 0. lower_bound for -5 gives index 0. upper_bound for 0 gives index 1, because 7 is the first value above 0. The range is ranks 0 only. Slot 0 holds 2, so the answer is 2.
• Count -3 to 7. lower_bound for -3 gives 0. upper_bound for 7 gives 2, because 10 is the first value above 7. The range is ranks 0 and 1. Slot 0 holds 2 and slot 1 holds 1, so the answer is 3.
• Count 8 to 1000. lower_bound for 8 gives index 2, because 10 is the first value that is at least 8. upper_bound for 1000 gives index 3. The range is rank 2, which holds 1. The answer is 1.
• Count -100 to -4. lower_bound for -100 gives 0 and upper_bound for -4 gives 0. The range is empty, so the answer is 0.

The last case shows why the code checks first < last before it calls the tree. Without that check, the program would ask for the sum over a range that ends before it starts.

Worked example 3: sums instead of counts

The third example changes the question. Instead of counting items, the program adds up their prices. The change is one line. In main, replace tree.add(rank, 1) with the next line.

tree.add(rank, op.a);

Nothing else changes. The ranks are the same, and the range checks are the same. Only the amount added to each slot is different. Each slot now holds the total of the prices that have that rank.

Here is a short input and the output from the changed program.

add 900000000
add 5
count 1 100
count 1 1000000000

$ ./sum_variant < input3.txt
5
900000005

The first count covers only the price 5, so the sum is 5. The second count covers both prices, so the sum is 5 + 900000000, which is 900000005.

This shows the general pattern. The tree can store any number that can be added, such as counts, sums, or the largest value in a range with a different combining rule. Coordinate compression decides where each value goes. The tree decides what is stored there.

Why the whole input is read first

The ranks depend on every value that will be stored. Suppose the program had built the sorted list after reading only add 5. Then 5 would get rank 0. If add 1 arrived later, the value 1 would need rank 0, and 5 would have to move to rank 1. Every slot that held a count for 5 would now be wrong.

The program avoids that trouble by reading the full input first. This works when all the data is available before the answers are needed, which is true for a file or a batch of queries.

When the values arrive one at a time and each answer is needed right away, a different structure is needed. The dynamic segment tree lesson later in this module covers that case. It builds nodes only where values appear, so it needs no full list in advance.

Cost

Let k be the number of add lines and q be the number of count lines.

• Sorting and removing repeats takes O(k log k) time.
• Each add line does one lower_bound search and one tree update. Both take O(log k) time.
• Each count line does two searches and one tree sum. All three take O(log k) time.

The total time is O((k + q) log k). The tree itself has about 4k slots. The sorted list holds at most k numbers.

Common mistakes

Using the raw value as the slot

A common mistake is to forget the rank mapping for add lines. Here the line tree.add(rank, 1) is replaced by the wrong line.

tree.add(static_cast<int>(op.a), 1);

The program compiles, but the compiler warns that rank is not used any more.

warning: unused variable 'rank' [-Wunused-variable]

The program also gives wrong answers. With the first example input, the output is wrong.

$ ./bug_nocompress < input1.txt
0
3
0
0

The correct output is 1, 3, 1, 0. The price 900000000 is used as a slot number. Every price here is above the tree's middle slot, so all of them land in the last slot. No error is shown. Check the output against a small example you can count by hand, and look for any place where a value is used as a slot.

Using upper_bound as the last rank

The end of a half-open range is not included. A common mistake is to pass that end to the sum as if it were included.

long long answer = (first < last) ? tree.sum(first, last) : 0;

Here last is the index of the first value above the range. Passing it to sum includes one extra rank. In the first example, the first count covers 1 to 100, so last is 2. The sum then includes rank 2, which holds 900000000.

$ ./bug_offbyone < input1.txt
2
3
2
0

The first line should be 1, and the third should be 1. The program runs without an error, so the mistake shows only in the output. Keep the - 1 in sum(first, last - 1).

Ignoring the empty range

When the lower bound and the upper bound give the same index, the range has no ranks. The code must return 0 in that case, and the check first < last in the program does that.

Reading queries as they come

The sorted list needs every stored value before the first answer. A program that tries to compress values as they arrive can find that the ranks of values it has already placed have changed. The fix is the one shown in this lesson: read the whole input first, or use a different structure.

Practice

1. Easy. The add lines arrive in this order: 1000, 7, 1000, 250. Write the sorted list of distinct values with each value's rank. How many slots does the tree need?

Show the answer

The sorted distinct list is 7, 250, 1000. The ranks are 0 for 7, 1 for 250 and 2 for 1000. The tree needs 3 slots.

2. Easy. The input is add 10, add 20, then count 10 15. What does the program print?

Show the answer

It prints 1. Only 10 is in the range from 10 to 15. The value 20 is above 15.

3. Medium. Use the sorted list 5, 42, 900000000 from the first example. Find the rank range for count 6 41 using lower_bound and upper_bound. Say whether the answer is 0 without asking the tree.

Show the answer

lower_bound for 6 returns index 1, because 42 is the first value that is at least 6. upper_bound for 41 returns index 1, because 42 is the first value above 41. The half-open range from 1 to 1 is empty. The answer is 0, and the tree does not need to be asked.

4. Medium. Change the program so that a count query returns the number of distinct prices in the range, not the number of items. For example, two items at price 5 should count as one. Hint: keep a std::vector<bool> that records which ranks have been used already, and add 1 to the tree only the first time a rank appears.

Show the answer

Add a vector named seen with one entry for each rank, all set to false. In the add branch, check seen[rank]. If it is false, set it to true and call tree.add(rank, 1). If it is already true, do nothing. With the input add 5, add 5, add 42, count 1 100, the answer is 2, because the prices 5 and 42 are the distinct values in range.

5. Hard. Explain why the program reads every add line before it builds the sorted list. Use the values 5 and 1 in your explanation.

Show the answer

Suppose the list was built after add 5 only. Then 5 would get rank 0. When add 1 arrives later, the value 1 must go before 5. That moves 5 to rank 1 and changes the meaning of the slot that held 5. Any count stored earlier would then be in the wrong place. Reading all the adds first gives each value its final rank before any slot is used.

Summary

• Coordinate compression maps the values that appear to ranks 0, 1, 2 and so on, keeping their order.
• A segment tree over ranks needs one slot per distinct value, not one slot per possible value.
• std::lower_bound gives the start of a value range and std::upper_bound gives the position after its end, so the rank range is half-open.
• Adding a number to a rank's slot can count items, add prices or store any other value that can be combined.
• The whole input must be known before the ranks are fixed, so this method works on a batch of data but not on a stream of values.