A persistent segment tree preserves all historical versions. After an update, you can query both the old and new versions.
Notice: updates only affect nodes (the path from root to leaf). Create new nodes only for this path; share all unchanged nodes with previous version.
def update(oldRoot, idx, val):
# Create new root
newRoot = copy of oldRoot
# Recurse, creating new nodes along the path
# Unchanged subtrees point to same nodes as old version
return newRoot
Space per update: new nodes. Total space for updates: .
Use case: answer queries about the array state after the -th update.