Intro

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: $O(n)$ per operation. Persistent approach: Create new nodes only for the changed parts. Share unchanged parts with previous versions.

Space: $O(\log n)$ per operation for tree structures. Persistent data structures keep all historical versions accessible.

After version $k$ operations, you can query any version $0$ to $k$. 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.