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

$ curl repovive.com/roadmaps/data-structures/wavelet-trees/count-less-than-in-range

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

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

$ curl repovive.com/roadmaps/data-structures/wavelet-trees/count-less-than-in-range

Repovive

Count Less Than in Range - Wavelet Trees | Data Structures | Repovive

Repovive.

Data Structures19 sections · 729 units49h total

Open in Course

Count Less Than in Range

Rank query

Count elements in $A[l..r]$ with value $< v$ :

function countLess(node, l, r, v)
 if l > r or v <= node.lo then
 return 0
 if node.hi < v then
 return r - l + 1

 mid := (node.lo + node.hi) / 2

 leftL := rank0(node.bitvector, l)
 leftR := rank0(node.bitvector, r + 1) - 1
 rightL := rank1(node.bitvector, l)
 rightR := rank1(node.bitvector, r + 1) - 1

 if v <= mid + 1 then
 return countLess(node.left, leftL, leftR, v)
 else
 leftCount := leftR - leftL + 1
 rightCount := countLess(node.right, rightL, rightR, v)
 return leftCount + rightCount

If $v$ is in the right half, all left subtree elements are less than $v$ .

Time: $O(\log \sigma)$ .