This is literally the same problem with 315. Count of Smaller Numbers After Self.

The only difference is to find count of numbers smaller than `half`

of the current number after itself.

To efficiently search for count of numbers smaller than a target, we can use a Binary Search Tree. There is a little change of the TreeNode to include count of numbers `smaller or equal`

to it. This will make the query even faster because we don't need to traverse all its left sub-tree to get the count.

Overall Algorithm:

- Scan the numbers from right to left.
- First search the tree to get
`count`

of numbers smaller than`nums[i] / 2.0`

, sum to the final result. - Insert
`nums[i]`

to the tree.

Insert logic:

- Recursively try to find a place to insert this number. When root is
`null`

, its time to create a new node. If meet the`same`

number, just increase the`count`

. - When try to insert the number to left sub-tree, increase
`count`

of current node.

Query logic:

- If target value is greater than the current value, meaning current node and all left sub-tree are
`smaller`

than target, return`count`

(remember it stands for count of numbers`smaller or equal`

to current number) of current node`plus`

any possible smaller number than target in`right`

sub-tree. - Otherwise, only search
`left`

sub-tree.

```
public class Solution {
class Node {
int value, count;
Node left, right;
Node (int v) {
value = v; count = 1;
}
}
public int reversePairs(int[] nums) {
int result = 0;
if (nums == null || nums.length <= 1) return result;
int len = nums.length;
Node root = new Node(nums[len - 1]);
for(int i = len - 2; i >= 0; i--) {
result += query(root, nums[i] / 2.0);
insert(root, nums[i]);
}
return result;
}
private Node insert(Node root, int value) {
if (root == null) return new Node(value);
if (root.value == value) {
root.count++;
}
else if (root.value > value) {
root.count++;
root.left = insert(root.left, value);
}
else {
root.right = insert(root.right, value);
}
return root;
}
private int query(Node root, double value) {
if (root == null) return 0;
if (value > root.value) {
return root.count + query(root.right, value);
}
else {
return query(root.left, value);
}
}
}
```