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

$ curl repovive.com/roadmaps/data-structures/persistent-data-structures/memory-analysis

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

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

$ curl repovive.com/roadmaps/data-structures/persistent-data-structures/memory-analysis

Repovive

Memory Analysis - Persistent Data Structures | Data Structures | Repovive

Repovive.

Data Structures19 sections · 729 units

Open in Course

Memory Analysis

How much space?

For persistent segment tree:

Initial tree: $O(n)$ nodes
Each update: $O(\log n)$ new nodes
$m$ updates: $O(n + m \log n)$ total nodes

For persistent array (as balanced tree):

Same analysis: $O(n + m \log n)$

For persistent Union-Find:

Uses persistent array internally
Same bounds apply

Comparison:

Structure	Space per update	Total for $m$ updates
Full copy	$O(n)$	$O(nm)$
Path copying	$O(\log n)$	$O(n + m \log n)$

Path copying saves a factor of $n / \log n$ for large $m$ .

HannahHi! I'm Hannah. Let me know if you need help understanding anything!