Count the number of inversions using Binary Indexed Tree in an array
def __init__(self, n):
        self.n = n + 1
        self.bit = [0] * self.n



bit has a well-known interpretation in programming which distracts from the intended interpretation here. IMO even something as generic as data would be better.




    def update(self, i, k):
        """Adds k to element with index i
        """
        while  i &lt;= self.n - 1:
            self.bit[i] += k
            i = i + (i &amp; -i)



The loop condition would be more familiar as while i &lt; self.n.

I don't see any reason to avoid +=.

A reference to explain the data structure would be helpful, because otherwise this is quite mysterious.




        mid = left + ((right - left) &gt;&gt; 1)



The reason for this particular formulation of the midpoint is to avoid overflow in languages with fixed-width integer types. Since that's not an issue in Python, I'd favour the more straightforward mid = (left + right) &gt;&gt; 1. It might even be a tiny bit faster.




    q = [ int( i ) for i in raw_input().strip().split() ]






    index = map(lambda t: binary_search(arr, t) + 1, q)



Why the inconsistency? I think it would be more Pythonic to use comprehensions for both.




    # Copy q and sort it.
    arr = sorted(deepcopy(q))

    # index array.
    index = map(lambda t: binary_search(arr, t) + 1, q)



This seems like a rather heavyweight approach. Why not just

    index = sorted((val, idx) for idx, val in enumerate(q))


?



Although asymptotically I don't see any reason why this would be \$\omega(n \lg n)\$, it has a few \$\Theta(n \lg n)\$ stages. The standard algorithm for this problem, which is essentially merge sort, has the same asymptotic complexity but probably hides a much smaller constant behind the \$\Theta\$ / \$O\$.