function countSmaller(nums):
// Coordinate compress
sorted_nums = sorted unique values of nums
rank = map each value v to its 1-based position in sorted_nums
n = sorted_nums.length
tree = array of size (n + 1), filled with 0
result = empty list
function query(i):
s = 0
while i > 0:
s += tree[i]
i -= i & (-i)
return s
function update(i):
while i <= n:
tree[i] += 1
i += i & (-i)
for num in nums from right to left:
r = rank[num]
result.append(query(r - 1))
update(r)
return result reversed
Time: . Space: .
Compare this to the segment tree solution. BIT is noticeably simpler.