# leetcode Count of Smaller Numbers After Self

### leetcode Count of Smaller Numbers After Self

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]`.

1. 使用逆序数有经典的解法为合并排序。
2. 用Fenwick树  关于Fenwick 树介绍 Binary indexed tree (Fenwick tree)
• 简单说就是看当前数在nums中排第几，然后对小于它的数求个数和
• 具体的做法是先离散化，确定每个数载nums中排到第几 （去重和排序）
• 然后从右向左扫描，每次统计比其小于1的个数（就是求和），然后把当前的数加入Fenwick中。

C++

## Binary indexed tree (Fenwick tree)

C++

Python

Leetcode , , , . permalink.

### 4 thoughts on “leetcode Count of Smaller Numbers After Self”

1. Xiaoye says:

你好博主，能不能对

for i in xrange(len(nums) – 1, -1, -1):
ans[i] = tree.sum(dic[nums[i]] – 1)