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

$ curl repovive.com/roadmaps/data-structures/persistent-data-structures/range-query-on-version

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

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

$ curl repovive.com/roadmaps/data-structures/persistent-data-structures/range-query-on-version

Repovive

Range Query on Version - Persistent Data Structures | Data Structures | Repovive

Repovive.

Data Structures19 sections · 729 units49h total

Open in Course

Range Query on Version

Standard segment tree query

Range queries work the same as regular segment trees:

function query(node, nodeL, nodeR, l, r)
    if node is null or r < nodeL or nodeR < l then
        return 0  // identity for sum

    if l <= nodeL and nodeR <= r then
        return node.sum

    mid := (nodeL + nodeR) / 2
    leftSum := query(node.left, nodeL, mid, l, r)
    rightSum := query(node.right, mid + 1, nodeR, l, r)
    return leftSum + rightSum

The only difference: you start from a specific version's root.

result := query(roots[version], 0, n - 1, l, r)

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