Memory Analysis

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:

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