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

$ curl repovive.com/roadmaps/data-structures/persistent-data-structures/count-in-range-solution

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

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

$ curl repovive.com/roadmaps/data-structures/persistent-data-structures/count-in-range-solution

Repovive

Count in Range Solution - Persistent Data Structures | Data Structures | Repovive

Repovive.

Data Structures19 sections · 729 units49h total

Open in Course

Count in Range Solution

Range query on two trees

function countInRange(nodeL, nodeR, nodeStart, nodeEnd, a, b)
    if nodeR is null or b < nodeStart or nodeEnd < a then
        return 0
    if a <= nodeStart and nodeEnd <= b then
        countR := nodeR.count if nodeR else 0
        countL := nodeL.count if nodeL else 0
        return countR - countL

    mid := (nodeStart + nodeEnd) / 2
    leftCount := countInRange(nodeL.left, nodeR.left, nodeStart, mid, a, b)
    rightCount := countInRange(nodeL.right, nodeR.right, mid + 1, nodeEnd, a, b)
    return leftCount + rightCount

Query: countInRange(roots[l], roots[r + 1], 0, maxVal, a, b)

Time: $O(\log n)$ per query.