Counting inversions with a Fenwick tree

Why it matters

Suppose you have a list of finish times for 100,000 runners, in the order they crossed the start line. You want to know how far the list is from being sorted. One simple measure is the number of pairs where a runner who started earlier finished later. That count is called the number of inversions. A sorted list has zero inversions. A list sorted from the largest value to the smallest has the most.

Counting inversions is a common interview problem, and it is also the core step of a well-known sorting method called merge sort. This lesson uses it to show a new use of a Fenwick tree. A Fenwick tree is a compact array that keeps running totals and lets the program update one total and read a prefix total in a few steps. The earlier lessons in this module used Fenwick trees for sums over a range. Here the Fenwick tree keeps a count of how many values of each size have been seen so far.

The direct method checks every pair, and that is too slow for 100,000 numbers. This lesson builds the faster method one step at a time. It starts with a small example you can check by hand, then shows the sweep, then the code, then two harder examples.

What an inversion is

An inversion is a pair of positions i and j where i comes before j in the list, but the value at i is bigger than the value at j. Two values are "out of order" when the bigger one comes first.

Take the list 3, 1, 2, 5, 4. Positions start at 0 in C++, so the values are at positions 0 to 4. Check each pair where the left value is bigger than the right value.

• 3 (position 0) and 1 (position 1): 3 is bigger and comes first. That is an inversion.
• 3 and 2 (position 2): an inversion.
• 3 and 5: 3 is smaller, so no.
• 5 (position 3) and 4 (position 4): 5 is bigger and comes first. That is an inversion.
• 1 and 2, 1 and 5, 1 and 4, 2 and 5, 2 and 4: none of these have the bigger value first.

So the list has 3 inversions. You can check this by hand in under a minute for five numbers. The job of the program is to get the same answer for a list with a hundred thousand numbers.

The slow method

The slow method checks every pair. For each position i, it looks at every later position j and counts when a[i] > a[j]. Here is that method. It is short, and it is the reference answer that the fast method must match.

long long countInversionsSlow(const vector<int>& a) {
    long long count = 0;
    for (size_t i = 0; i < a.size(); ++i) {
        for (size_t j = i + 1; j < a.size(); ++j) {
            if (a[i] > a[j]) {
                ++count;
            }
        }
    }
    return count;
}

For n numbers, the program makes n * (n - 1) / 2 comparisons. For 5 numbers that is 10 comparisons. For 100,000 numbers it is about 5 billion comparisons. A modern computer can run a few billion simple comparisons per second, so 5 billion comparisons still takes seconds, and the time grows with the square of n. Doubling the input makes the work four times as large. The fast method below does about n * log n steps instead, which for 100,000 numbers is roughly 1.7 million steps.

The sweep idea

Instead of looking at pairs, look at one position at a time, moving from left to right. When the program reaches position j, it asks one question: how many numbers before j are bigger than a[j]? Each of those numbers forms one inversion with a[j]. Add up that count for every j, and you have the total.

The question "how many earlier numbers are bigger than x" can be answered with two counts that are easy to keep:

• The number of earlier numbers in total. This is just the position j, because positions 0 to j - 1 are all earlier.
• The number of earlier numbers that are less than or equal to x.

Subtract the second count from the first, and the result is the number of earlier numbers that are bigger than x. The subtraction is easier to see with the numbers from the example.

Here is the walk through 3, 1, 2, 5, 4. Before each step, the program knows which values it has already passed.

The last column adds up to 0 + 1 + 1 + 0 + 1 = 3. That matches the count from the pair check.

The problem left is the middle column. Keeping a plain list of earlier values and counting through it on every step would be the slow method again. The Fenwick tree solves this. It stores counts by value, so the program can ask "how many earlier values are at most x" in a few steps, even when the list is long.

What a Fenwick tree does

A Fenwick tree is an array that stores running totals in a special pattern. It is also called a binary indexed tree. Positions run from 1 to n, and it supports two operations, each taking about log n steps:

• add: add a number to the count at one position.
• prefix: get the total of all counts at positions 1 up to some position p.

You do not need to know how the pattern is chosen to use the tree. The one detail that matters is the step size. From position p, the program moves to p + (p & -p) when adding and to p - (p & -p) when reading. The expression p & -p gives the lowest set bit of p, which is the largest power of two that divides p. Each step removes or moves one set bit of the position, so a walk to the end or to the start takes at most about log2(n) steps. For n = 100,000, log2(n) is about 17.

Here is the class used in the program. It is small enough to read in one go.

class Fenwick {
public:
    explicit Fenwick(int n) : n_(n), tree_(n + 1, 0) {}
 
    // Add delta to the count at position pos.
    void add(int pos, int delta) {
        for (; pos <= n_; pos += pos & -pos) {
            tree_[pos] += delta;
        }
    }
 
    // Return the total of the counts at positions 1 through pos.
    int prefix(int pos) const {
        int total = 0;
        for (; pos > 0; pos -= pos & -pos) {
            total += tree_[pos];
        }
        return total;
    }
 
private:
    int n_;
    vector<int> tree_;
};

The tree_ vector has n + 1 cells, and cell 0 is never used. That keeps the arithmetic simple, because positions start at 1.

For this problem, the counts stored in the tree are "how many times has each value appeared so far". If the program adds 1 at the position of x after each step, then prefix(r) gives the number of earlier values with rank at most r. With r set to the rank of x, that is exactly the middle column in the table above.

Turning values into ranks

The Fenwick tree needs positions from 1 to n, but the values in the list can be any integers. A list might contain 100, 7, 42, and 7. The value 100 cannot be used as a position in a tree with 4 cells.

The fix is to replace each value with its rank. The rank is the place the value takes among the distinct values, counted from 1. For the list 100, 7, 42, 7, the distinct values in order are 7, 42, 100. So 7 has rank 1, 42 has rank 2, and 100 has rank 3. The list becomes 3, 1, 2, 1. The order of the values is kept, and the numbers are now small.

The program does this with a sorted copy of the values. It sorts the copy, removes repeats with unique, and uses lower_bound to find where each value sits. Ranks are only a relabelling, so the answer does not change. The lesson on coordinate compression later in this module covers the same idea in more depth.

The code

Here is the full program. It contains the Fenwick tree, the fast count, the slow count for checking, and a test with 2,000 random lists.

Compile and run it with these commands.

g++ -std=c++20 -Wall -o inversions inversions.cpp
./inversions

The program prints the following.

example: 3
sorted: 0
reversed: 6
with equal values: 2
random trials mismatches: 0

The first line matches the hand count of 3. The sorted list has no inversions, and the reversed list of 4 numbers has every pair out of order, which is 4 * 3 / 2 = 6 pairs. The last line says that the fast method matched the slow method in all 2,000 random lists.

Three details in the code are worth a close look.

The line inversions += processed - seen.prefix(rank); is the heart of the method. processed is the number of earlier elements. seen.prefix(rank) is the number of earlier elements that are at most x. Their difference is the number of earlier elements bigger than x.

The line seen.add(rank, 1); runs after the count. This order matters. If the program added x first, then x would be counted as one of the earlier elements that are at most x, and the result would be one short for every element.

The variable inversions has type long long, which is a 64-bit integer. The largest possible count is n * (n - 1) / 2. For n = 70,000 that is 2,449,965,000, which is larger than the largest 32-bit int, about 2.1 billion. Using long long for the total avoids overflow.

A second example: equal values

Equal values need a rule. Two equal numbers are not out of order, because neither one is bigger than the other. So the pair 2, 2 is not an inversion.

Take the list 2, 2, 1. The pairs are:

• The first 2 and the second 2: equal, not an inversion.
• The first 2 and 1: an inversion.
• The second 2 and 1: an inversion.

The answer is 2. The program gets this right because seen.prefix(rank) counts every earlier value that is at most x, and that includes earlier values equal to x. So an equal earlier value is removed from the "bigger" count.

If a programmer forgets this and asks for values strictly less than x, the answer goes wrong. That version is in the mistakes section below, where its output is shown.

A third example: a longer list with repeats

Look at the list 100, 7, 42, 7. It has 4 numbers and repeats the value 7. Here is the expected answer, checked by hand. The pairs where the left value is bigger than the right value are:

• 100 with 7 (position 1): inversion.
• 100 with 42: inversion.
• 100 with 7 (position 3): inversion.
• 42 with 7 (position 3): inversion.

That is 4 inversions. The 7 at position 1 and the 7 at position 3 are equal, so they are not counted. The fast method ranks the values as 3, 1, 2, 1, and it finds the same 4 inversions. The slow method also prints 4 for this list, which is the check that matters.

The point of the third example is that the values in the list are large, but the ranks are small. The Fenwick tree has only 3 cells for this list, even though the values go up to 100. For a list of 100,000 values that are all different, the tree has 100,000 cells, and that is still small.

Common mistakes

Mistake 1: counting equal pairs as inversions. The list 2, 2, 1 should give 2. If the query line is changed to seen.prefix(rank - 1), which counts only values strictly less than x, the program prints 3 for that list, and the copy with that one change printed 3 when it was run. The earlier 2 is no longer taken away from the "bigger" count, so the pair of two equal 2 values is counted as an inversion. The correct answer is 2.

Mistake 2: starting the Fenwick tree at position 0. The tree positions must start at 1. If the code calls add(0, 1), the step pos += pos & -pos never moves, because 0 & -0 is 0. The loop runs forever. A small test loop that starts at position 0, run under timeout 2, did not finish and was stopped with exit code 124. Use ranks that start at 1, as the code above does.

Mistake 3: using raw values as positions. A list with the value 1000000000 cannot use that number as a position. The tree would need about one billion cells, which takes several gigabytes of memory, and a negative value would write outside the array, which C++ treats as undefined behaviour. Always convert values to ranks first.

Mistake 4: a compile error when the constructor is not given a size. The class has an explicit constructor that takes the size n. If the code writes Fenwick seen; with no size, the compiler stops with this message (the first lines, from a real compile of a small test file with the same constructor; the line numbers depend on the file):

nodefault.cpp: In function ‘int main()’:
nodefault.cpp:14:13: error: no matching function for call to ‘Fenwick::Fenwick()’
   14 |     Fenwick seen;
      |             ^~~~
nodefault.cpp:5:14: note: candidate 1: ‘Fenwick::Fenwick(int)’
    5 |     explicit Fenwick(int n) : n_(n), tree_(n + 1, 0) {}
      |              ^~~~~~~
nodefault.cpp:5:14: note: candidate expects 1 argument, 0 provided

The fix is to pass the number of distinct values, as the code does: Fenwick seen(static_cast<int>(sorted_values.size()));.

Practice

Exercise 1. Count the inversions in the list 4, 3, 2, 1 by hand. Then count them with the formula for a fully reversed list of n numbers.

Show the answer

The list has 4 numbers. Every pair is out of order, so there are 6 pairs: (4,3), (4,2), (4,1), (3,2), (3,1), (2,1). The formula n * (n - 1) / 2 gives 4 * 3 / 2 = 6. The program printed 6 for this list.

Exercise 2. Count the inversions in the list 2, 3, 1, 2. List the pairs before you check your answer.

Show the answer

The pairs where the left value is bigger than the right value are: 2 (position 0) with 1 (position 2), 3 (position 1) with 1 (position 2), and 3 (position 1) with 2 (position 3). The pair 2 (position 0) and 2 (position 3) is equal, so it is not counted. The answer is 3, and the program prints 3 for this list.

Exercise 3. Write the rank of each value in the list 10, 3, 10, 7. Use the rule from the lesson: the rank is the place among the distinct values, starting at 1.

Show the answer

The distinct values in order are 3, 7, 10. So 3 has rank 1, 7 has rank 2, and 10 has rank 3. The list becomes 3, 1, 3, 2. Both 10 values get rank 3, because they are equal.

Exercise 4. In the sweep loop, the program calls seen.add(rank, 1) after it reads seen.prefix(rank). Explain what would go wrong if the two lines were swapped.

Show the answer

If the program added x first, then prefix(rank) would include x itself. Every element would then count itself as "earlier and at most x", so each element's count would be one smaller than it should be. The first element would count -1, and for the list 3, 1, 2, 5, 4 the total would be 3 minus 5 (one less for each of the 5 elements), which is -2.

Exercise 5. The list has 100,000 numbers, and each one is different. Estimate how many comparisons the slow method makes, and how many steps the fast method makes, in round numbers. Use log2(100000) is about 17.

Show the answer

The slow method makes 100,000 * 99,999 / 2, which is about 5 billion comparisons. The fast method does about 100,000 loop steps in the sweep, and each step does one prefix query and one add. Each of those walks about 17 cells, so the total is roughly 100,000 times 2 times 17, or about 3.4 million cell visits. That is more than a thousand times fewer steps.

Summary

• An inversion is a pair of positions where the left value is bigger than the right value. A sorted list has none.
• The slow method checks every pair and takes time that grows with the square of the list length.
• The sweep method goes left to right. For each value, it counts the earlier values that are bigger, using "earlier total" minus "earlier and at most x".
• A Fenwick tree keeps counts by rank, so the "at most x" count takes about log n steps instead of a full scan.
• Replace values with ranks first, and use long long for the total, since the count can grow past the range of a 32-bit int.