Algorithm:
Coordinate compress values to range
Process array right to left
For each element : query prefix sum up to (count of smaller elements seen)
Update position with
def countInversions(arr):
# Coordinate compress
sorted_arr = sorted(set(arr))
rank = {v: i+1 for i, v in enumerate(sorted_arr)}
n = len(sorted_arr)
bit = [0] * (n + 1)
inversions = 0
for x in reversed(arr):
r = rank[x]
# Count elements smaller than x (already processed = to the right)
inversions += query(r - 1)
update(r, 1)
return inversions
Time: . Space: .