Immutable does not mean you have to copy the whole structure. You can store only the changes. This is how immutable data structures work in functional languages such as Haskell.
Also, for nested data structures you need to either do path copying, or use "modification boxes" [1].
[1] https://en.wikipedia.org/wiki/Persistent_data_structure#Tech...