# 315. Count of Smaller Numbers After Self

对每个元素找它后面比它小的元素个数。找前面或后面比它大/小元素的题可以用BST或Binary Index Tree做。BIT能以O(lgN)时间query（含）指定index前所有元素的和，并且能任意更改元素的值而不影响查询区域和的时间，具体实现比较tricky, 可以参考[花花的视频](https://link.zhihu.com/?target=https%3A//www.youtube.com/watch%3Fv%3DWbafSgetDDk%26t%3D939s)。利用BIT的性质，要O(lg(N))时间查出一个和，这个和直接就是个数。因此BIT相当于在统计频率, index对应成（唯一）元素值，每个index存的值就是针对这个值的个数。所以先统计出所有可能的元素的值，排序并根据值分配它在BIT里的index，这样一次query就能把值小于它的全部统计出来。因为要统计后面的，所以从后往前遍历。

```cpp
/*
 * @lc app=leetcode id=315 lang=cpp
 *
 * [315] Count of Smaller Numbers After Self
 *
 * https://leetcode.com/problems/count-of-smaller-numbers-after-self/description/
 *
 * algorithms
 * Hard (39.01%)
 * Likes:    1364
 * Dislikes: 62
 * Total Accepted:    87.5K
 * Total Submissions: 223.1K
 * Testcase Example:  '[5,2,6,1]'
 *
 * 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:
 * 
 * 
 * Input: [5,2,6,1]
 * Output: [2,1,1,0] 
 * Explanation:
 * 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.
 * 
 */
class BIT {
public: 
    BIT(const int N): sums(N + 1, 0) {}

    void update(int i, int delta) {
        while (i < sums.size()) {
            sums[i] += delta;
            i += lowbit(i); 
        }
    }

    int query(int i) const {
        int sum = 0;
        while (i > 0) {
            sum += sums[i];
            i -= lowbit(i);
        }
        return sum;
    }
    static inline int lowbit(int x) {return x & (-x);}
    vector<int> sums;
};

class Solution {
public:
    vector<int> countSmaller(vector<int>& nums) {
        // sort the unique numbers
        set<int> sorted(nums.begin(), nums.end());
        // map the number to the BIT index.
        unordered_map<int, int> indices;
        int index = 0;
        // 小于等于num的个数
        for (const int num : sorted) indices[num] = ++index;
        vector<int> res;
        // tree的index是rank, val/sums[i]是rank<=i的count。
        BIT tree(indices.size());
        for (int i = nums.size() - 1; i >= 0; --i) {
            // 找出有多少个数 < num_i
            res.push_back(tree.query(indices[nums[i]] - 1));
            // 把num_i所代表的index的count + 1
            tree.update(indices[nums[i]], 1);
        }
        reverse(res.begin(), res.end());
        return res;
    }
};


```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://hao-fu-1.gitbook.io/oj/binary_tree_and_divide_conquer/315.-count-of-smaller-numbers-after-self.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.