#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/data-structures/wavelet-trees/count-smaller-solution

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/data-structures/wavelet-trees/count-smaller-solution

Repovive

Count Smaller Solution - Wavelet Trees | Data Structures | Repovive

Repovive.

Data Structures19 sections · 729 units49h total

Open in Course

Count Smaller Solution

Implement your solution

The BIT approach is recommended for this problem:

function countSmaller(nums)
    // Coordinate compress
    sorted := sort(unique(nums))
    rank := map value to index

    result := []
    bit := BIT of size len(sorted)

    for i from n - 1 down to 0
        r := rank[nums[i]]
        result.append(bit.query(r - 1))
        bit.update(r, 1)

    return reverse(result)

Process right to left. Query counts smaller (indices 0 to r-1), then mark current value.

Time: $O(n \log n)$ . Space: $O(n)$ .