def countSmaller(nums):
# Coordinate compress
sorted_nums = sorted(set(nums))
rank = {v: i+1 for i, v in enumerate(sorted_nums)}
n = len(sorted_nums)
tree = [0] * (n + 1)
result = []
def query(i):
s = 0
while i > 0:
s += tree[i]
i -= i & (-i)
return s
def update(i):
while i <= n:
tree[i] += 1
i += i & (-i)
for num in reversed(nums):
r = rank[num]
result.append(query(r - 1))
update(r)
return result[::-1]
Time: . Space: .
Compare this to the segment tree solution—BIT is noticeably simpler.