Why This Design Works and How a Fenwick Tree Simplifies Inversion Counting

An inversion pair consists of two elements (a, b) in an array where a appears before b and a > b. For example, in the array [30,10,40,20] the pairs (30,10), (30,20) and (40,20) are inversions.

Naïve O(n²) solution

The straightforward method scans each element and compares it with every element to its right, counting how many smaller elements follow it. Applied to the example array, the algorithm finds three inversion pairs.

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

arr = [5, 2, 6, 1]
print(count_inversions_brutal(arr))

More clever right‑to‑left method

Instead of two nested loops, process the array from right to left, keeping a list of elements already seen. For each new element, count how many of the previously seen elements are smaller.

Example walk‑through on [5,2,6,1]:

Start with 1 → seen = [1]; smaller count = 0.

Next 6 → seen = [1,6]; smaller count = 1 (the 1).

Next 2 → seen = [1,6,2]; smaller count = 1 (the 1).

Next 5 → seen = [1,6,2,5]; smaller count = 2 (1 and 2).

def count_inversions_simple(arr):
    n = len(arr)
    count = 0
    seen = []
    for i in range(n-1, -1, -1):
        current = arr[i]
        smaller_count = sum(1 for x in seen if x < current)
        count += smaller_count
        seen.append(current)
    return count

arr = [5, 2, 6, 1]
print(count_inversions_simple(arr))

While easier to understand than the brute‑force approach, this method still requires O(n²) time for large inputs because the sum scan over seen is linear.

Fenwick (Binary Indexed) Tree optimization

A Fenwick tree acts as a compact counter that supports prefix‑sum queries and point updates in O(log n) time. By discretizing the array values to a small integer range, the tree can efficiently track how many smaller elements have been seen.

Discretization example for [5,2,6,1]: after sorting and removing duplicates we obtain [1,2,5,6] with ranks 1‑4.

data:   '1'  '2'  '5'  '6'
position: 1   2   3   4

Processing the original array from right to left:

1 → no smaller elements; update rank 1.

6 → query prefix sum up to rank‑1 (3) → 1 smaller element; update rank 4.

2 → query up to rank‑1 (1) → 1 smaller element; update rank 2.

5 → query up to rank‑1 (2) → 2 smaller elements; update rank 3.

The tree maintains counts at each position, allowing each query and update to run in logarithmic time.

def count_inversions(arr):
    sorted_arr = sorted(set(arr))
    rank = {v: i+1 for i, v in enumerate(sorted_arr)}
    n = len(arr)
    bit = [0] * (n + 1)
    count = 0
    for i in range(n-1, -1, -1):
        curr_rank = rank[arr[i]]
        small_count = 0
        idx = curr_rank - 1
        while idx > 0:
            small_count += bit[idx]
            idx -= (idx & -idx)
        count += small_count
        idx = curr_rank
        while idx <= n:
            bit[idx] += 1
            idx += (idx & -idx)
    return count

arr = [5, 2, 6, 1]
print(count_inversions(arr))

Summary

The example demonstrates how a Fenwick tree combined with discretization and reverse traversal yields an O(n log n) algorithm for counting inversion pairs. The key steps are:

Discretization : map array values to a compact rank range.

Reverse traversal : ensure each query only sees elements that appear to the right of the current element.

Fenwick updates and queries : use the tree to record occurrences and retrieve the count of smaller elements efficiently.