938. Count of Smaller Numbers After Self (BST/BIT)

Given an integer array, return a new array where each element is the count of numbers to its right that are strictly smaller than it. Use a Binary Indexed Tree (or balanced BST) over ranks for an efficient solution. The input is a JSON array.

Input: A JSON array of integers.

Output: Array — counts of smaller elements to the right.

Examples

Input: [5,2,6,1]
Output: [2,1,1,0]
Explanation: Counts of smaller elements to the right.

Input: [-1,-1]
Output: [0,0]
Explanation: No smaller elements.

Input: [0]
Output: [0]
Explanation: Single element.

Constraints

• 0<=n<=10^5
• -10^4<=value<=10^4

Asked by