# Count of Smaller Numbers After Self

<https://leetcode.com/problems/count-of-smaller-numbers-after-self/description/>

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

## Thoughts

1. 问比它的数小的个数，可以想到BST中从root到它所有要往左的节点数目和路径上每个节点的左子树数目的和。
2. 节点中除了存值，还存左子树节点数。每次插入一个新节点到左边时，更新parent的这个值
3. 问右边比小的个数，那就从右往左建树，树中即所有在它右边的数
4. 有数重复的情况。因此还要一个dup, 默认应该为1.

## Code

```
class Solution {
    struct TreeNode {
        TreeNode *left, *right;
        int val, scount, dup;
        TreeNode(int x) : val(x), scount(0), dup(1), left(NULL), right(NULL) {}
    };

public:
    vector<int> countSmaller(vector<int>& nums) {
        int n = nums.size();
        vector<int> res(n, 0);
        if (n == 0) return res;
        TreeNode* root = new TreeNode(nums[n - 1]);
        for (int i = n - 2; i >= 0; i--) {
            int scount = 0;
            insert(root, nums[i], scount);
            res[i] = scount;
        }
        return res;
    }

private:
    void insert(TreeNode *node, int num, int& scount) {
        if (num < node->val) {
            ++node->scount;
            if (!node->left) {
                node->left = new TreeNode(num);
            } else {
                insert(node->left, num, scount);
            }
        } else if (num > node->val) {
            scount += node->scount + node->dup;
            if (!node->right) {
                node->right = new TreeNode(num);
            } else {
                insert(node->right, num, scount);
            }
        } else {
            scount += node->scount;
            ++node->dup;
        }
    }
};
```

```
class Solution {
    class TreeNode {
        int val, smallerCount, dup = 1;
        TreeNode left, right;
        TreeNode(int val, int smallerCount) {
            this.val = val;
            this.smallerCount = smallerCount;
        }
    }

    int count = 0;
    private TreeNode insert(TreeNode node, int num, int smallerCount) {
        if (node == null) {
            count = smallerCount;
            return new TreeNode(num, 0);
        }
        if (num < node.val) {
            node.smallerCount++;
            node.left = insert(node.left, num, smallerCount);
        } else if (num > node.val) {
            node.right = insert(node.right, num, smallerCount + node.smallerCount + node.dup);
        } else {
            node.dup++;
            count = smallerCount + node.smallerCount;
        }
        return node;
    }

    public List<Integer> countSmaller(int[] nums) {
        List<Integer> res = new ArrayList<>();
        TreeNode root = null;
        for (int i = nums.length - 1; i >= 0; i--) {
            count = 0;
            root = insert(root, nums[i], 0);
            res.add(0, count);
        }

        return res;
    }
}
```

## Analysis

Errors:

1. 忘了加当node.val == nums\[i]时的smallerCount.

树balance时, 时间复杂度O(NlgN).

## Ver.2

Iterative建树

```
class Solution {
    class TreeNode {
        int val, dup, smallerCount;
        TreeNode left, right;

        TreeNode(int val) {
            this.val = val;
            dup = 1;
            smallerCount = 0;
        }
    } 

    private int add(TreeNode root, int num) {
        int res = 0;
        TreeNode node = root;
        while (node != null) {
            if (num < node.val) {
                node.smallerCount++;
                if (node.left == null) {
                    node.left = new TreeNode(num);
                    break;
                } else {
                    node = node.left;
                }
            } else if (num > node.val) {
                res += node.smallerCount + node.dup;
                if (node.right == null) {
                    node.right = new TreeNode(num);
                    break;
                } else {
                    node = node.right;
                }
            } else {
                res += node.smallerCount;
                node.dup++;
                break;
            }
        }

        return res;
    }

    public List<Integer> countSmaller(int[] nums) {
        List<Integer> res = new ArrayList<>();
        if (nums.length == 0) {
            return res;
        }

        TreeNode root = new TreeNode(nums[nums.length - 1]);
        res.add(0);
        for (int i = nums.length - 2; i >= 0; i--) {
            res.add(0, add(root, nums[i]));
        }
        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/binary-search-tree/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.