Persistent Data Structures
Used in Functional Programming languages for efficient implementation of immutable data structures
This is an example of a Persistent Array
Looks like an m-tree
Elements at the leaf are the actual array elements
Say we want to replace n with Q.
In this case, we only need to make copies of only 3 blocks (highlighted in red), and rest of the blocks will be reused in the new variable.
In practical cases, an m-tree with 32 elements per block are used.
Calculate how many elements it can hold with just an height of 3