Binary Indexed Tree Count Inversions

Problem

Count the inversions in a list using a binary indexed tree.

An inversion is a pair i < j with nums[i] > nums[j] using strict comparison. Compress the values to ranks and use a BIT to track how many values have been seen so far. For each element, every previously seen value with a larger rank is an inversion.

Return the inversion count.

Hint

seen minus the count of values less than or equal to the current rank gives the inversions for that element.

Test cases

case 1

in: [[2,4,1,3,5]]

expected: 3

case 2

in: [[5,4,3,2,1]]

expected: 10

case 3

in: [[1,2,3]]

expected: 0

case 4

in: [[]]

expected: 0

case 5

in: [[1,1]]

expected: 0

Starter codePython

def count_inversions(nums):
    # Your code here
    pass

5 test cases · run your code against them in the editor