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

$ curl repovive.com/roadmaps/data-structures/persistent-data-structures/version-queries-solution

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

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

$ curl repovive.com/roadmaps/data-structures/persistent-data-structures/version-queries-solution

Repovive

Version Queries Solution - Persistent Data Structures | Data Structures | Repovive

Repovive.

Data Structures19 sections · 729 units49h total

Open in Course

Version Queries Solution

Persistent segment tree

class VersionedArray:
    roots: list of segment tree roots
    n: int

    function __init__(arr)
        roots := [build(arr, 0, n - 1)]

    function update(index, value)
        newRoot := persistentUpdate(roots.last(), 0, n - 1, index, value)
        roots.append(newRoot)

    function query(version, l, r)
        return rangeSum(roots[version], 0, n - 1, l, r)

Each update appends a new root. Queries access the appropriate version's root.

Time: $O(\log n)$ per operation. Space: $O(n + m \log n)$ for $n$ initial elements and $m$ updates.