Persistent Data Structures: Path Copying, Fat Nodes & Fractional Cascading Time Travel

Path Copying vs Fat Nodes vs Sleator–Tarjan Node-Splitting Method

Driscoll, Sarnak, Sleator, and Tarjan (1989) formalized four levels of persistence and three structural implementation techniques:

1. Path Copying (Functional / Purely Immutable Persistence — Okasaki 1998): Every node is strictly immutable. Modifying a leaf allocates a new leaf and recursively allocates a new copy of each ancestor up to a new root roots[version], sharing all unmodified sibling subtrees. Achieves Full Persistence with $O(\log N)$ time and $O(\log N)$ space per update, and zero synchronization locks across concurrent reader threads!
2. Fat Nodes: Instead of copying ancestor nodes, allow each node to store an arbitrarily long version-stamped modification history mods = [(v₁, field, val₁), (v₂, field, val₂), ...]. Uses $O(1)$ space per update, but looking up a pointer at version $v$ requires binary searching the node's modification log, slowing down every pointer dereference by $O(\log M)$!
3. Sleator–Tarjan Bounded In-Degree Node Splitting (1989): Combines the $O(1)$ space of Fat Nodes with the $O(1)$ pointer traversal of Path Copying! For any pointer-based data structure where every node has bounded in-degree $\le k$ (for a tree without parent pointers, in-degree is $1$), give each node $2k$ extra modification slots (mods). As long as a node has a free mod slot, updates take $O(1)$ space without copying; when a node overflows its $2k$ slots, split (clone) the node and propagate pointer updates to its $\le k$ predecessors. By potential analysis with $\Phi$ proportional to full mod slots, this achieves $O(1)$ amortized space and $O(1)$ slowdown per pointer step!

Implementation: Arena-Backed Persistent Treap with $O(\log N)$ Path-Copying Split/Merge

// C++20: Purely Functional Persistent Treap using Contiguous Bump-Arena Path Copying
#include <vector>
#include <cstdint>
#include <utility>

class PersistentTreapArena {
    struct Node {
        int key;
        uint64_t prio;
        int left = 0, right = 0; // 0 = null sentinel index in pool
    };
    std::vector<Node> pool;

    int cloneNode(int u) {
        pool.push_back(pool[u]);
        return static_cast<int>(pool.size()) - 1;
    }

public:
    PersistentTreapArena() { pool.push_back({0, 0, 0, 0}); } // Index 0 is null

    int newNode(int key, uint64_t prio) {
        pool.push_back({key, prio, 0, 0});
        return static_cast<int>(pool.size()) - 1;
    }

    // Non-destructively splits version root 'u' into (L, R) by cloning only the O(log N) spine
    std::pair<int, int> splitPersistent(int u, int key) {
        if (u == 0) return {0, 0};
        int copy = cloneNode(u);
        if (pool[copy].key <= key) {
            auto [L, R] = splitPersistent(pool[copy].right, key);
            pool[copy].right = L;
            return {copy, R};
        } else {
            auto [L, R] = splitPersistent(pool[copy].left, key);
            pool[copy].left = R;
            return {L, copy};
        }
    }
};