Persistent and Functional Data Structures

Persistence, path copying, immutable structures, persistent segment trees, versioned arrays, persistent tries, rollback DSU, and applications to historical queries.

Persistence, path copying, immutable structures, persistent segment trees, versioned arrays, persistent tries, rollback DSU, and applications to historical queries. Distinguish full, partial, and confluent persistence conceptually.

Partial persistence: every old version can be queried; only the newest can be updated.

Full persistence: any version can be updated, creating a branch.

Confluent persistence: versions can also be merged.

Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2):

Path copying: an update creates new copies of the O(log n) nodes on the root-to-leaf path and shares every other node with the previous version, so each version costs O(log n) extra memory. The rollback DSU omits path compression because compression changes many parents and could not be undone cheaply; union by size alone keeps finds O(log n).

#include <bits/stdc++.h>
using namespace std;

// persistent segment tree over value ranks: version i = counts of the first i array elements.
// k-th smallest in a[l..r] = walk versions r+1 and l together, using count differences.
struct Node { int left, right, count; };
vector<Node> t{{0, 0, 0}};                                     // node 0 is the shared empty tree
int insert(int prev, int lo, int hi, int pos) {
    int cur = (int)t.size(); t.push_back(t[prev]); ++t[cur].count;      // copy only the path from the root
    if (hi - lo > 1) {
        int mid = (lo + hi) / 2;
        if (pos < mid) { int c = insert(t[prev].left, lo, mid, pos); t[cur].left = c; }
        else { int c = insert(t[prev].right, mid, hi, pos); t[cur].right = c; }
    }
    return cur;
}
int kth(int u, int v, int lo, int hi, int k) {                 // u = version l, v = version r+1
    if (hi - lo == 1) return lo;
    int mid = (lo + hi) / 2, leftCount = t[t[v].left].count - t[t[u].left].count;
    return k < leftCount ? kth(t[u].left, t[v].left, lo, mid, k) : kth(t[u].right, t[v].right, mid, hi, k - leftCount);
}

int main() {
    vector<int> a = {5, 1, 9, 3, 7, 3, 8, 2};
    vector<int> vals = a; sort(v
…

2nd smallest in a[2..6] {9,3,7,3,8} = 3
nodes: 32 for 8 versions (each insert adds about log2(7) + 1 nodes)
2000 random k-th smallest range queries match sorting
after 3 unions, connected(0,2) = true; after one rollback = false

Quiz

? What does path copying copy on an update?
+ Only the nodes on the path from the root to the changed leaf :: Everything else is shared with the old version.
- The whole tree :: That would be O(n) per version.
- Nothing :: Old versions would change.
- Only the leaf :: Ancestors' aggregates change too.

? Why does a rollback DSU skip path compression?
+ Compression rewrites many parent pointers, which would be expensive to undo; union by size keeps finds O(log n). :: Each union changes exactly one parent.
- Compression is incorrect. :: It is correct, just not undoable cheaply.
- To save memory. :: Not the reason.
- It does not; it uses both. :: It cannot easily.

? Partial persistence means…
+ any version can be read, only the latest updated :: Full persistence allows updating old versions too.
- only the latest version exists :: That is ephemeral.
- versions can be merged :: That is confluent.
- nothing can be updated :: Then there would be one version.