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

$ curl repovive.com/roadmaps/data-structures/persistent-data-structures/kth-number-building

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

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

$ curl repovive.com/roadmaps/data-structures/persistent-data-structures/kth-number-building

Repovive

Kth Number: Building - Persistent Data Structures | Data Structures | Repovive

Repovive.

Data Structures19 sections · 729 units49h total

Open in Course

Kth Number: Building

Create versions incrementally

Build persistent segment tree version by version:

function build(arr)
    // Coordinate compress
    sorted := sort(unique(arr))
    rank := map value to index
    maxVal := len(sorted) - 1

    // Empty tree as version 0
    roots := [buildEmpty(0, maxVal)]

    // Add elements one by one
    for i from 0 to len(arr) - 1
        r := rank[arr[i]]
        newRoot := update(roots[i], 0, maxVal, r, +1)
        roots.append(newRoot)

    return roots

Version $i$ represents prefix $A[0..i-1]$ . Version 0 is empty. Version $n$ contains all elements.