You update a data structure. Later, you need to query its state before that update. What do you do? Naive approach: Copy the entire structure before each update.
Space: per operation. Persistent approach: Create new nodes only for the changed parts. Share unchanged parts with previous versions.
Space: per operation for tree structures. Persistent data structures keep all historical versions accessible.
After version operations, you can query any version to . In this section, I'll teach you persistence for arrays, segment trees, and other structures. You'll learn path copying, the fat node method, and applications to problems requiring version history.