Counting inversions with a Fenwick tree in Python

Why this matters

Suppose two judges rank the same five dancers. If the judges agree, the two lists put every pair of dancers in the same order. Each pair that the judges order differently is a disagreement. Counting those disagreements is a standard way to measure how far apart two rankings are.

The same count also measures how much work a simple sort does. An adjacent swap is a swap of two neighbouring values. Each adjacent swap fixes exactly one out-of-order pair, and insertion sort, which is the sort many people learn first, makes exactly as many adjacent swaps as there are out-of-order pairs in the list.

A pair of positions i and j is an inversion when i comes before j and the value at i is bigger than the value at j. The word inversion just means "reversed pair". The number of inversions is the number of such pairs.

The direct way to count them checks every pair. For a list of n values there are n * (n - 1) / 2 pairs. For 100000 values that is 4999950000 pairs, which is nearly 5 billion checks. That is too slow for a large input, even before Python's speed is taken into account.

This lesson gives a faster method. It runs in O(n log n) time, which means the work grows a little faster than the length of the list, but far slower than the square of it. The method uses a Fenwick tree. The module lesson on lazy propagation and Fenwick trees covers that structure in detail. This lesson recalls only the parts it needs.

You should be comfortable with lists, for loops and integers. Python integers have no fixed size, so a count never wraps around. A later section shows where the size of a number can still cause trouble.

Inversions in a small example

Take the list [3, 1, 2]. Its positions are 0, 1 and 2. Check each pair of positions in order.

Positions 0 and 1 hold 3 and 1. The first value is bigger, so this pair is an inversion.

Positions 0 and 2 hold 3 and 2. The first value is bigger, so this is also an inversion.

Positions 1 and 2 hold 1 and 2. The first value is smaller, so this pair is not an inversion.

The list has 2 inversions. The brute force method is a loop over all pairs:

def brute_force(values):
    count = 0
    for i in range(len(values)):
        for j in range(i + 1, len(values)):
            if values[i] > values[j]:
                count += 1
    return count

This code is correct. It is also slow for large lists, because the two loops together run n * (n - 1) / 2 times. The rest of the lesson keeps the same answer and makes the work per value much smaller.

The sweep: count each value's inversions when you reach it

Walk through the list from left to right. Think about the value x at position j. Every value before j has already been seen. There are exactly j of those earlier values.

Some earlier values are less than or equal to x. The rest are greater than x. Each greater earlier value forms an inversion with x, because it comes before x and is bigger. Each earlier value that is less than or equal to x forms no inversion with x.

So the number of new inversions created by x is:

number of earlier values minus the number of earlier values that are less than or equal to x

Look at [3, 1, 2] again with this rule.

When the walk reaches 3, there are no earlier values. It adds 0 inversions.

When the walk reaches 1, there is one earlier value, the 3. No earlier value is less than or equal to 1. The new inversions are 1 minus 0, which is 1. That is the pair (3, 1).

When the walk reaches 2, there are two earlier values, the 3 and the 1. One of them, the 1, is less than or equal to 2. The new inversions are 2 minus 1, which is 1. That is the pair (3, 2).

The total is 0 + 1 + 1 = 2, which matches the direct count.

The rule is simple. The hard part is answering "how many earlier values are less than or equal to x?" quickly. A plain loop over the earlier values takes time proportional to the position, so the whole walk would again take about n * n / 2 steps. The Fenwick tree answers that question in about log n steps, so the walk takes n times log n steps in total.

The tree is laid out along the values, from smallest to largest. When a value is seen, its cell gets a count of 1. When a value is asked about, the tree adds up the counts for all values up to and including it.

Turning values into ranks

The Fenwick tree positions must be the whole numbers 1, 2, 3 and so on up to the number of distinct values. Raw values such as -5 or 1000000 cannot be used as positions directly.

The fix is a rank. The rank of a value is its place in the sorted list of distinct values, counted from 1. Equal values get the same rank.

For the values 10, -5, 7, 7 the distinct sorted list is -5, 7, 10. So the ranks are:

• -5 has rank 1.
• 7 has rank 2, both times it appears.
• 10 has rank 3.

Python can build this list and look up ranks with the standard bisect module:

from bisect import bisect_left
 
sorted_distinct = sorted(set(values))
rank = bisect_left(sorted_distinct, v) + 1

bisect_left returns the index of the value in the sorted list, counting from 0. Adding 1 turns that index into a rank counted from 1. The value v is always in the list, because the list was built from the same values, so the search always finds it. A separate lesson in this module covers coordinate compression, which is the general name for this kind of mapping.

Ranks keep the order of the values. If a is less than b, then the rank of a is less than the rank of b. That order is all the counting needs.

The Fenwick tree in brief

A Fenwick tree is a list of counts with a special way of finding its cells. It is also called a binary indexed tree. Its two operations are:

• add(i, delta) adds delta to the count at position i.
• prefix_sum(i) returns the total of all counts at positions 1 through i.

Both operations use the same trick. Each cell tree[i] stores the total for a block of positions. The block length is the value of i & -i, which is the lowest 1 bit of i.

The & symbol means "bit by bit and" and the - in -i means negative. You do not need to understand the bit arithmetic in full to use the tree. The rule you need is this: i & -i is the largest power of two that divides i.

Here are some examples:

• Cell 6 has 6 & -6 equal to 2. So cell 6 stores the total for positions 5 and 6.
• Cell 4 has 4 & -4 equal to 4. So cell 4 stores the total for positions 1 through 4.
• Cell 5 has 5 & -5 equal to 1. So cell 5 stores only position 5.

To add to position i, the tree updates cell i, then moves to i + (i & -i), and repeats until the index passes the size of the tree. Take a tree of size 8 and add to position 5. The steps are:

• Position 5. Cell 5 covers position 5 only.
• Position 6, because 5 + 1 is 6. Cell 6 covers positions 5 and 6.
• Position 8, because 6 + 2 is 8. Cell 8 covers positions 1 through 8.
• Stop, because 16 is past the size.

Those three cells are the ones that contain position 5 in their block, so they are the cells that must change.

To get the prefix sum up to i, the tree reads cell i, then moves to i - (i & -i), and repeats until the index reaches 0. Take prefix_sum(7) on the same tree. The steps are:

• Position 7. Cell 7 covers position 7 only.
• Position 6, because 7 - 1 is 6. Cell 6 covers positions 5 and 6.
• Position 4, because 6 - 2 is 4. Cell 4 covers positions 1 through 4.
• Stop, because 0 is reached.

Those three cells together cover positions 1 through 7 with no overlap, and their total is the prefix sum.

The prefix loop removes the lowest 1 bit of the index at each step, and the add loop carries past it. Either way the number of steps is at most the number of bits in the index. The index of a tree of size 100000 has at most 17 bits, so each operation takes at most about 17 steps.

The first full program

The program below holds a list of values and prints its number of inversions. To use your own list, change the line that sets values.

The output is:

inversions: 3

Check the answer by hand. The list is 2, 4, 1, 3, 5. The pairs are (2, 1), (4, 1) and (4, 3). Those are the three inversions. Nothing else is out of order.

Here is what the code does, line by line.

The Fenwick class holds the list tree. It has size size + 1 because the tree uses positions 1 to size, and cell 0 is never used.

count_inversions builds the sorted list of distinct values and creates a tree with one position per distinct value. The loop walks through the values in order. For each value it asks the tree how many earlier values have a rank less than or equal to this one, and stores that in not_greater. The number of earlier values is seen. Their difference is the count of earlier values that are greater, and that difference is added to inversions. After that the value's own rank is added to the tree, and seen goes up by one.

The order inside the loop matters. The query comes before the add. The Common mistakes section shows what happens when the order is swapped.

A trace of every step

The next program prints the state of each step for two small lists. It is the same method, with extra printing, so you can follow the numbers.

The output is:

values [3, 1, 2], sorted distinct [1, 2, 3]
value 3 rank 3 | earlier 0, earlier <= it 0, new inversions 0, running total 0
value 1 rank 1 | earlier 1, earlier <= it 0, new inversions 1, running total 1
value 2 rank 2 | earlier 2, earlier <= it 1, new inversions 1, running total 2
total inversions: 2
 
values [2, 4, 1, 3, 5], sorted distinct [1, 2, 3, 4, 5]
value 2 rank 2 | earlier 0, earlier <= it 0, new inversions 0, running total 0
value 4 rank 4 | earlier 1, earlier <= it 1, new inversions 0, running total 0
value 1 rank 1 | earlier 2, earlier <= it 0, new inversions 2, running total 2
value 3 rank 3 | earlier 3, earlier <= it 2, new inversions 1, running total 3
value 5 rank 5 | earlier 4, earlier <= it 4, new inversions 0, running total 3
total inversions: 3

In the second list, the value 1 creates 2 new inversions. Both earlier values, 2 and 4, are greater than 1. The value 3 creates 1 new inversion, with the 4 that came before it. The value 5 creates none, because nothing before it is bigger.

Worked example two: equal values

Equal values are not an inversion. The pair (2, 2) has the first value equal to the second, not greater, so it is not counted.

Take the list [2, 2, 1]. The pairs are (2, 2), which is not an inversion, and two pairs (2, 1), each of which is an inversion. The answer is 2.

This is why the program uses counts.prefix_sum(rank) and not the count of values strictly below the rank. A value's own earlier copies are "less than or equal to it", so they are subtracted, and they add nothing to the total.

To check this in the program, change values to [2, 2, 1]. The output is inversions: 2, which matches the hand count.

Worked example three: a longer list

The last example has a mix of negative values and repeated values. Take the list [10, -5, 7, 7]. Its ranks are 3, 1, 2 and 2, as shown earlier.

The pairs are (10, -5), (10, 7) and (10, 7), which are the inversions. The pair (-5, 7) is not one, and neither is the pair (7, 7).

Change values to [10, -5, 7, 7]. The output is inversions: 3.

A reversed list gives the largest count for its length. Every pair is an inversion, so the answer is n * (n - 1) / 2. For [5, 4, 3, 2, 1] that is 10. Set values to [5, 4, 3, 2, 1] and the output is inversions: 10. Use this check when you test your own changes. If the reversed list gives the wrong count, the bug is in the counting code.

Checking the method against brute force

A fast method can still be wrong on rare inputs. The safe habit is to compare it with the slow method on many random lists. The program below does that. It uses a fixed random seed, so the same numbers come out every time you run it.

The output is:

random lists checked: 3000 mismatches: 0

The random values run from -20 to 20, so there are many repeated values. Each list has up to 59 values. The check covers empty lists, lists with one value and lists with many equal values, which are the cases where mistakes usually hide.

Common mistakes

Adding the value before asking the question

The order inside the loop matters. Suppose the add happens first:

counts.add(rank, 1)
not_greater = counts.prefix_sum(rank)
inversions += seen - not_greater

Now the query counts the current value itself as "less than or equal to". The number of greater earlier values is too small by one. The result can even go negative.

Run the count with this order on the list [1, 2, 3]. The answer is -3. The correct answer is 0, because the list is already sorted. A negative count is a clear sign that the order of the two lines is wrong.

Making the tree one cell too short

The tree uses cells 1 to size, so the list must hold size + 1 cells. A common slip is to write [0] * size. The first update at position size then goes past the end of the list.

The program below has this slip on purpose.

size = 4
tree = [0] * size
i = 4
tree[i] += 1
print("added position 4")

Python prints this error and stops:

Traceback (most recent call last):
  File "/path/to/short.py", line 4, in <module>
    tree[i] += 1
    ~~~~^^^
IndexError: list index out of range

The last line says that an index was out of range for the list. The line above it shows the code that failed, and the marks under tree[i] point at the index. Index 4 is the last valid position for the tree, so the list needs length 5. The fix is [0] * (size + 1).

Starting the tree at position 0

Position 0 is not a valid position in a Fenwick tree. The add loop moves by i & -i, and for i = 0 that value is 0. So the index never increases, and the loop never ends.

The program below shows the first step. It is stopped by a timeout after three seconds, because the loop never ends, so the last print never runs. Do not run it without a timeout.

tree = [0] * 5
size = 4
position = 0
print("starting add at position 0", flush=True)
i = position
while i <= size:
    tree[i] += 1
    i += i & -i
print("finished")

The output is the first line only:

starting add at position 0

The word finished never appears. The fix is to convert values to ranks that start at 1, as the + 1 in bisect_left(sorted_distinct, v) + 1 does.

Expecting big counts to lose precision

Python integers have no fixed size, so the count of inversions never wraps around. The reversed list of 100000 values gives the exact answer, 4999950000, with no special handling.

A float is different. Dividing with / gives a float, and a float holds only about 15 to 16 exact digits. Above 2**53 some whole numbers cannot be stored exactly. The number 2**53 + 1 becomes 2**53 when it is turned into a float, so float(2**53 + 1) == 2**53 is True. Use // for whole-number division, as the formula n * (n - 1) // 2 does, so that the count stays an exact integer.

Practice

1. Count the inversions in the list [5, 2, 4, 1] by hand. Then check your answer with the first program.

Show the answer

There are 5 inversions. The pairs are (5, 2), (5, 4), (5, 1), (2, 1) and (4, 1). The pair (2, 4) is not an inversion, because 2 is smaller. The first program prints inversions: 5 for this list.

2. Give the rank of every value in the list [10, -5, 7, 7], using the method in this lesson.

Show the answer

The distinct sorted list is -5, 7, 10. So 10 has rank 3, -5 has rank 1, and both 7 values have rank 2.

3. In a Fenwick tree of size 8, list the cells that add(5, 1) changes, in order. Then list the cells that prefix_sum(7) reads, in order.

Show the answer

add(5, 1) changes cells 5, 6 and 8, in that order. The index goes 5, then 5 + 1 = 6, then 6 + 2 = 8, and then stops, because 16 is past the size. prefix_sum(7) reads cells 7, 6 and 4, in that order. The index goes 7, then 7 - 1 = 6, then 6 - 2 = 4, and then stops at 0.

4. Change the rule so that equal values also count as inversions, that is, pairs with a[i] >= a[j]. What does the count become for the list [2, 2, 1]?

Show the answer

The answer is 3. The pair (2, 2) now counts, and the two pairs (2, 1) still count. To make the program do this, the count of earlier values that are less than or equal to the value must be replaced by the count of earlier values that are strictly less than it. The Fenwick query at rank - 1 gives that count.

5. Explain in one or two sentences why the query must happen before the add.

Show the answer

The query asks how many earlier values are less than or equal to the current value. If the current value were already in the tree, it would be counted in that answer, so the number of greater earlier values would be too small. The add must come after the query, so that only earlier values are in the tree.

Summary

• An inversion is a pair of positions i < j where the value at i is greater than the value at j. Equal values are not inversions.
• Sweep left to right. For each value, the new inversions are the number of earlier values minus the number of earlier values that are less than or equal to it.
• Use ranks from 1 up to the number of distinct values as Fenwick positions, so the tree stays small and the order is kept.
• Query before adding, and make the tree list one cell longer than its size.