The data structures in Clojure are built on shallow 32-way trees. When you "change" a map or a vector, the algorithm only copies from the root node down to the parent of the leaf you're changing. That's log32(N) copied nodes in a tree of N nodes total.

Because persistent data structures that use structural sharing.

Good answers by others. The cost it not quite zero, but very close. The benefits this buys are huge. The obvious case is recursive search algorithms.