LeetCode Q315: Count of Smaller Numbers After Self (hard)

You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].

Example:

Given nums = [5, 2, 6, 1]

To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.

Return the array [2, 1, 1, 0].

Solution:

I refer to this post for a solution using  BST. The basic idea is to use node in a tree to save information about how many nodes met already are smaller. 

I actually tried several solutions and for both of them I use node to save the number of nodes that appear after current node. However, saving information in this way force you have to update subtree of current when a node that is smaller than current node. This results in a TLE.

Instead, we should use node to save how many nodes are in the left of current node, which will not require an update of subtree.

Using mergesort, please refer to this post, and also geeksforgeeks's post. Code is given below:


Using binary indexed tree:
可以使用BIT来解这道题。 假设我们的输入数组是nums={5, 6, 3, 2}, 我们同样从数组的最后一项开始处理。第一个拿出来的是[2]。 我们希望，可以通过BIT的add操作加一个数字1到所有在[2]左边且比[2]大的数中去。可是我们如何才能知道哪些数是比[2]大的呢？ 这个就需要我们对原数组先进行一次排序， 排序后我们得到sorted_nums={2, 3, 5, 6}, 而我们的目的是得到原数组元素在排序后数组的位置places={2, 3, 1, 0}。到此位置，sorted_nums的任务就结束了，我们在程序中就用不到它了。继续我们的操作，此时我们取出来的是[2]， 然后我们找到它在places中对应位置的数[0]。 我们对[0]调用一次add操作(意义在于，我们希望对排序后比[2]大的数据都加1。也就是对排序后排在1, 2, 4位的数都加1， 这里没有3是因为BIT add 操作的原理，之后在算range_query的时候3就等于1+2的内容）。 然后我们就可以调用sum操作计算[2]这个位置的答案了。 之后拿出来的[3], [6]，都可以作同样的操作。 下一位拿出来的是[5], 此时，[5]的places值是2， 那么要向排序后排在[5]之后的数字加1，也就是向排在第2位之后的数字加1。这样的话，我们可能会要向[6]这个位置的加1, 可是这个时候我们不用担心结果出错，因为[6]这个位置的数我们已经处理结束了，即使可能向它加1，我们在处理5的sum操作的时候也只会看[5]排序后位置之前的数字。