Reverse Pairs Solution

The tricky part: coordinate compression must include both $nums[i]$ and $2 \cdot nums[j]$ values.

function reversePairs(nums):
    // Collect all values needed
    all_vals = set of all values in nums
    for x in nums:
        all_vals.add(2 * x)
    sorted_vals = sorted list of all_vals
    rank = map each value v to its 1-based position in sorted_vals

    n = sorted_vals.length
    tree = array of size (n + 1), filled with 0
    result = 0

    for num in nums from right to left:
        // Query: how many 2*elem values in tree are < num
        r = rank[num]
        result += query(r - 1)
        // Update: add 2*num for future left-side queries
        update(rank[2 * num])

    return result

Process right to left. For each $nums[i]$, query how many $2 \cdot nums[j]$ values (from elements to its right) fall below $nums[i]$. Time: $O(n \log n)$. Space: $O(n)$.