# Count the number of inversions using Binary Indexed Tree in an array

Original Problem: HackerRank

I am trying to count the number of inversions using Binary Indexed Tree in an array. I've tried to optimise my code as much as I can. However, I still got TLE for the last 3 test cases. Any ideas that I can further optimise my code?

# Enter your code here. Read input from STDIN. Print output to STDOUT
#!/usr/bin/python

from copy import deepcopy

class BinaryIndexedTree(object):
"""Binary Indexed Tree
"""
def __init__(self, n):
self.n = n + 1
self.bit = [0] * self.n

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

def count(self, i):
"""Returns the sum from index 1 to i
"""
total = 0
while i > 0:
total += self.bit[i]
i = i - (i & -i)

def binary_search(arr, target):
"""Binary Search
"""
left, right = 0, len(arr) - 1
while left <= right:
mid = left + ((right - left) >> 1)
if target == arr[mid]:
return mid
elif target < arr[mid]:
right = mid - 1
else:
left = mid + 1

return -1

T = input()
for iterate in xrange(T):
n = input()
q = [ int( i ) for i in raw_input().strip().split() ]

# Build a Binary Indexed Tree.
bit = BinaryIndexedTree(n)

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

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

# Loop.
for i in xrange(n - 1, -1, -1):
bit.update(index[i] + 1, 1)

• Does #!/usr/bin/python even work if it's not on the first line of the file? – Mast Jun 4 '19 at 13:32
• @Mast It'll not work if you run that on your local machine using ./ to your script name. I guess that's just a prompt (the first line) of HackerRank online editor, and HackerRank will take care of running it correctly behind the scene. – Jason Jun 5 '19 at 2:35

    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 <= self.n - 1:
self.bit[i] += k
i = i + (i & -i)


The loop condition would be more familiar as while i < 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) >> 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) >> 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\$$.

I'm pretty sure you can replace

def count(self, i):
"""Returns the sum from index 1 to i
"""
total = 0
while i > 0:
total += self.bit[i]
i = i - (i & -i)


with

def count(self, i):
return sum(self.bit[i] for i in range(1,i))


also,

mid = left + ((right - left) >> 1)


is the same as

mid = (right + left) >> 1

• Not sure which of the docstring (and thus your interpretation) or the original code is wrong, but while i > 0: i = i - (i & -i) is NOT the same as range(1, i). – 301_Moved_Permanently Jul 10 '16 at 20:07
• I think it's a docstring problem, what do you want i - (i & -i) to do? – Oscar Smith Jul 10 '16 at 20:21
• I don't want it to do anything, it's just not performing i -> 1. For instance, with i = 31 it goes 31 -> 30 -> 28 -> 24 -> 16 -> 0: it removes the least significant bit at each iteration. – 301_Moved_Permanently Jul 10 '16 at 20:27
• oh. Then for the first piece, all I'd change is i=i-... to i-=... – Oscar Smith Jul 10 '16 at 20:52