In this post, we will solve the problem of counting inversions in an array using Fenwick Trees.
What Is Inversion Count?
In computer science, an inversion is defined as a pair of indices (i, j) in an array arr[ ] such that:
- i < j and,
- arr[i] > arr[j]
In simpler terms, an inversion indicates that two elements in the array are out of their expected order (assuming ascending order). The inversion count indicates how “unsorted” the array is.
Problem Statement
Given an array arr[] of integers, find the total number of inversions. For example:
Input: [1, 3, 3, 2, 2]
Output: 4
Explanation
There are 4 inversions:
3 (arr[1]), 2 (arr[3])
3 (arr[1]), 2 (arr[4])
3 (arr[2]), 2 (arr[3])
3 (arr[2]), 2 (arr[4])
Naive Approach
A brute force method to count inversions involves comparing every pair of elements in the array using two nested loops.
Pseudocode
1. inversionCount = 0
2. for i = 0 to arr.size() - 1:
3. for j = i + 1 to arr.size():
4. if arr[i] > arr[j]:
5. inversionCount += 1
6. return inversionCount
Code Implementation
int countInversions(vector<int>& arr) {
int inversionCount = 0;
for (int i = 0; i < arr.size() - 1; i++) {
for (int j = i + 1; j < arr.size(); j++) {
if (arr[i] > arr[j]) {
inversionCount++;
}
}
}
return inversionCount;
}
Time Complexity: O(n2)
The algorithm compares all pairs in the array, making it inefficient for large datasets.
Space Complexity: O(1)
No extra space is needed apart from the array itself.
While straightforward, this approach becomes impractical for large arrays due to its quadratic time complexity.
Fenwick Tree Approach
Before implementing the solution, let’s first understand a bit about Fenwick Trees.
The Fenwick Tree, also known as the Binary Indexed Tree (BIT), is a data structure that efficiently computes prefix sums and supports updates in logarithmic time. Fenwick Tree supports two operations:
- Query: Computes the prefix sum up to a given index.
- Update: Modifies the value at a specific index and updates all affected nodes.
Fenwick Tree has already been discussed in detail in a previous post – Fenwick Tree (Binary Indexed Tree)
How to use Fenwick Tree for Inversion Count?
In the context of inversion counting, Fenwick Tree allows us to:
- Quickly find the cumulative count of elements smaller than the current element.
- Update the frequency of elements as they are processed.
Pseudocode
1. Normalize the array so that all elements are mapped to ranks [1, n].
2. Initialize an empty Fenwick Tree with size n.
3. inversionCount = 0
4. for i = n - 1 to 0:
5. Query the Fenwick Tree for the cumulative count of all the elements
smaller than the current element that have already appeared
inversionCount += BIT.query(arr[i] - 1)
6. Update the Fenwick Tree to record the occurrence of current element,
incrementing its count by 1
BIT.update(arr[i], 1)
7. return inversionCount
Code Implementation
//
// main.cpp
// Inversion Count
//
// Created by Himanshu on 13/12/24.
//
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// Fenwick Tree implementation
class FenwickTree {
vector<int> BIT;
int n;
public:
// Constructor to initialize Fenwick Tree of size n
FenwickTree(int size) {
n = size;
BIT.assign(n+1, 0); // Initialize tree with 0 values
}
void update(int idx, int delta) {
while (idx <= n) {
BIT[idx] += delta;
idx += idx & -idx;
}
}
int query(int idx) {
int sum = 0;
while (idx > 0) {
sum += BIT[idx];
idx -= idx & -idx;
}
return sum;
}
};
int countInversions(vector<int>& arr) {
int n = (int) arr.size();
// Normalize the array
vector<int> sortedArr = arr;
sort(sortedArr.begin(), sortedArr.end());
for (int& x : arr) {
x = (int) (lower_bound(sortedArr.begin(), sortedArr.end(), x) - sortedArr.begin()) + 1;
}
// Initialize Fenwick Tree
FenwickTree BIT(n);
int inversionCount = 0;
// Count inversions
for (int i = n - 1; i >= 0; i--) {
inversionCount += BIT.query(arr[i] - 1); // Count elements smaller than arr[i] that have already appeared
BIT.update(arr[i], 1); // Update BIT to record the occurrence of arr[i], incrementing its count by 1
}
return inversionCount;
}
int main() {
vector<int> arr = {1, 3, 3, 2, 2};
cout << countInversions(arr) << " inversions" << endl;
return 0;
}
Output
4 inversions
Explanation of the Algorithm
Fenwick Tree approach transforms the inversion counting problem into two main operations: prefix sum queries and incremental updates. By iterating through the array from right to left, the algorithm efficiently tracks and counts inversions in logarithmic time for each element. Let’s understand it in detail.
Normalization
Normalization transforms the array values into ranks ranging from 1 to n, making them compatible with Fenwick Tree indexing. It replaces each value with its relative position in the sorted array — where the smallest value becomes 1, the second smallest becomes 2, and so on. This ensures that all values are positive integers within the valid range of indices supported by the Fenwick Tree, enabling efficient operations like prefix sum queries and updates. Normalization also handles duplicate values by assigning them the same rank, preserving the original order of elements for inversion counting.
Example
arr = {1, 3, 3, 2, 2}
After normalization
arr = {1, 4, 4, 2, 2}
In the above code, lower_bound() is used for normalization. It is important to note that C++ lower_bound(first, last, val) returns an iterator to the first element in the range [first,last) that is not less than val.
Note: std::lower_bound function in C++ requires the container to be sorted in ascending order for it to work correctly. It uses a binary search algorithm to locate the first element in the range that is not less than the specified value.
Let’s understand how normalization works:
We create a sorted copy sortedArr[] of input array arr[]. And then we iterate the input array arr[] and replace each value with its rank in the input array using sortedArr[].
Consider the above array arr[] and its sorted version sortedArr[].
sortedArr[]
index: 0 1 2 3 4
value: 1 2 2 3 3
arr[]
index: 0 1 2 3 4
value: 1 3 3 2 2
Normalization
This is how the array arr[] is normalized:
Array after normalization:
{1, 4, 4, 2, 2}
arr[0] = 1 (rank 1)
This is because '1' is the smallest element in the array
arr[1] = 4 (rank 4)
This is because '3' ranks 4th after 1, 2, 2
arr[2] = 4 (rank 4)
This is because '3' ranks 4th after 1, 2, 2
arr[3] = 2 (rank 2)
This is because '2' ranks 2nd after 1
arr[4] = 2 (rank 2)
This is because '2' ranks 2nd after 1
Next, we’ll understand how Fenwick Tree helps find the inversion count.
Querying and Updating the Fenwick Tree for Counting Inversions
To calculate the inversion count using a Fenwick Tree, the process involves querying and updating the tree as you traverse the input array from right to left. Here’s how it works,
Iterate the input array from right to left and for each element:
- Query the Fenwick Tree to get the cumulative count of all the elements smaller than the current element that have already been processed. This provides the number of inversions contributed by the current element.
- Update the Fenwick Tree to record the count of the current element, essentially increasing its count by ‘1’ in the Fenwick Tree. This keeps the track of the frequency of all elements processed so far for inversion counting.
The combination of efficient querying and incremental updates enables inversion counting in logarithmic time, resulting in an overall time complexity of O(nlogn). This approach leverages the Fenwick Tree’s ability to dynamically maintain prefix sums, making it an efficient solution for the inversion counting problem.
Time Complexity
- Normalization: O(nlogn) (sorting and mapping)
- Processing Each Element: Each query and update operation takes O(logn), resulting in an overall time complexity of O(nlogn).
Overall Time Complexity: O(nlogn)
Space Complexity
- Fenwick Tree: O(n)
- Auxiliary Storage: O(n) space to store the sorted version of the array, required for normalization.
Overall Space Complexity: O(n)
Counting inversions using Fenwick Trees is an efficient method, reducing the time complexity from O(n2) with the naive method to O(nlogn). Also, the above approach using Fenwick Trees can efficiently track and count inversions even for a continuous stream of data.