Count of smaller numbers after self with Fenwick tree — how to coordinate compress?

Question presented to candidate: "Given an integer array, return an array where counts[i] is the number of elements to the right of index i that are strictly smaller than nums[i]. Values can be negative and as large as a billion, and the array can have 100,000 elements. Solve it in Python with a Fenwick tree — and explain how you deal with the value range."

What a strong answer should cover:

• The O(n²) brute force first, and why n = 10^5 needs O(n log n).
• The right-to-left scan: the answer for i is a prefix count of values already seen, then add nums[i].
• How a Fenwick tree does point add and prefix sum in O(log n) with i & -i, and why it is 1-indexed.
• Coordinate compression: sorted distinct values, 1-based ranks, equal values sharing a rank, and prefix(rank − 1) for strictly smaller.
• Alternatives: merge sort counting, a segment tree, a BST with subtree sizes.
• Python details: sorted(set(nums)) and a dict comprehension for ranks (or bisect.bisect_left), a list of size m + 1, and no overflow concerns for totals.

Clarifying questions expected:

• What is the value range — can values be negative or very large?
• Do equal values count as smaller?
• How large can n be?

Code / implementation expected: Yes — compression plus a Fenwick tree in Python, O(n log n) time and O(n) space.