Data Structures19 sections · 729 units
Open in Course

Space Optimization

Reducing memory usage

Persistent structures use more memory than ephemeral ones. Optimization techniques:

Garbage collection: Remove unreachable old versions.

Keep only versions you might query.

Reference counting: Track how many versions reference each node.

Delete nodes with zero references.

Compaction: Periodically rebuild heavily-modified structures to reduce sharing overhead.

Memory pools: Pre-allocate node memory to reduce allocation overhead.

In competitive programming, memory is usually sufficient. In production, these optimizations matter.