Inversions with a BIT
Count out-of-order pairs efficiently.
What Is an Inversion?
An inversion is a pair i < j where a[i] > a[j]. It is a single out-of-order pair, and counting them measures how unsorted an array is.
Why Inversions Matter
Inversion count equals the number of swaps a bubble sort would make. Contest problems hide it inside ranking and disorder questions.