Rollback Data Structures

Why Rollback Data Structures Matters

In dynamic graph algorithms, backtracking searches, and offline query processing, algorithms frequently modify a data structure, solve a localized sub-problem, and then must revert the data structure to its exact state prior to those modifications. While fully persistent data structures allow querying and mutating any historical version at any time, they incur significant memory and execution overhead through continuous path-copying ($O(\log N)$ space and time per update) and complex pointer management.

Rollback Data Structures provide a lightweight alternative for Last-In, First-Out (LIFO) mutation workflows. By maintaining an explicit history log (an "undo stack") of modified array cells or struct fields, a rollback structure can undo operations in exact reverse order. When applied to structures like Disjoint Set Union (DSU)—by combining union-by-rank with the deliberate omission of path compression—rollback mechanisms revert state transitions in time proportional to the number of operations performed, requiring only $O(1)$ auxiliary stack space per mutation.

Rollback data structures maintain an undo stack of overwritten memory locations, enabling LIFO state restoration without the overhead of full persistence. By avoiding operations that mutate state during read queries (such as path compression in DSU), rollback structures guarantee deterministic $O(\log N)$ operation bounds and $O(1)$ memory overhead per reverted modification.

Core Concepts and Terminology

Understanding rollback data structures requires distinguishing between state mutation, state persistence, and state restoration.

A rollback data structure consists of two primary layers:

The Primary Structure: A deterministic data structure (e.g., a tree or array-based DSU) configured such that write operations modify a strictly bounded number of memory slots per operation.
The Undo Stack: A LIFO history stack recording tuples of (address/index, previous_value) before any mutation takes place.

When a checkpoint (or snapshot) is requested, the current size of the undo stack is recorded. To rollback to a checkpoint, the engine pops entries from the undo stack and writes previous_value back into address until the undo stack shrinks to the recorded checkpoint size.

Key Term	Definition	Role in Algorithm	Example
Undo Stack	A LIFO collection recording prior variable states before mutations occur.	Stores modifications for exact step-by-step unrolling.	`history.push({addr, old_val})`
Checkpoint / Snapshot	An integer representing the depth of the undo stack at a specific point in time.	Defines the target stack size for a rollback operation.	`cp = history.size()`
Rollback	The process of popping undo stack entries and writing old values back to memory until stack size equals target checkpoint.	Restores primary data structure to a historical state.	Reverts `parent[1]` back to `1`.
Union-by-Rank / Size	A DSU balancing heuristic that attaches smaller trees under larger trees.	Guarantees $O(\log N)$ tree height without requiring path compression.	Attach tree of size 1 under tree of size 2.
Path Compression Hazard	The anti-pattern of compressing paths during read (`find`) operations in a rollback structure.	Mutates parent pointers during queries, corrupting the undo stack with $O(N)$ write noise.	Disallowed in rollback DSU.

How Rollback Data Structures Works, Step by Step

To execute operations with rollback capabilities, a data structure must implement three core mechanics: Guarded Writes, Snapshot Creation, and LIFO Reversal.

1. Guarded Writes

Whenever an internal array entry or variable is modified during an operation (such as updating parent[root_u] = root_v or size[root_v] += size[root_u]), the system creates a history entry recording the array reference, index, and original value before overwriting it.

2. Snapshot Creation

A snapshot does not copy data arrays. Instead, it queries and returns the integer length of the undo stack. This $O(1)$ operation marks a logical version bound.

3. LIFO Reversal (Rollback)

To revert to a snapshot length $K$:

While history.size() > K:
Pop entry (var_ref, index, old_val) from history.
Restore var_ref[index] = old_val.
Restore auxiliary counters (e.g., component count) associated with the reverted operation.

The control flow logic for Union, Snapshot, and Rollback operations is structured as follows:

Rollback Data Structures control flow

flowchart TD
A[Client Operation Call] --> B{Operation Type}

```
B -->|union u, v| C[find u without path compression]
C --> D[find v without path compression]
D --> E{root_u == root_v?}
E -->|Yes| F[No-op: nodes already connected]
E -->|No| G[Union-by-Size: balance roots]
G --> H[Push old parent and size to Undo Stack]
H --> I[Update parent, size, and decrement component count]

B -->|snapshot| J[Return current history.size]

B -->|rollback_to checkpoint| K{history.size > checkpoint?}
K -->|Yes| L[Pop top mutation frame]
L --> M[Revert parent and size values]
M --> N[Increment component count]
N --> K
K -->|No| O[Target Snapshot State Restored]

```

Worked Example with a Full Trace

Consider a Rollback DSU with $N = 5$ elements ($0, 1, 2, 3, 4$), initially forming 5 isolated components.

We trace the following sequence of operations:

union(0, 1)
union(2, 3)
Save snapshot_1
union(1, 2)
union(3, 4)
rollback_to(snapshot_1)
rollback_to(0)

Worked Example

Trace It by Hand

Scenario: A graph initially contains $N = 5$ isolated vertices ($0, 1, 2, 3, 4$). You process the following sequence:

union(0, 1)
union(2, 3)
Save snap1
union(1, 2)
union(3, 4)
Call rollback_to(snap1)

Predict the outcome:

What is the number of connected components after step 5?
What is the status of connected(0, 4) after step 5?
What is the number of connected components after step 6?
What is the status of connected(0, 4) and connected(0, 1) after step 6?

Answer Verification:

After step 5: All 5 vertices are joined into 1 component.
connected(0, 4) is True (path $0 \to 1 \to 2 \to 3 \to 4$ exists).
After step 6: Stack rolls back to snap1 (2 operations reverted: union(3, 4) and union(1, 2)). Component count is 3 ($\{0, 1\}, \{2, 3\}, \{4\}$).
connected(0, 4) is False; connected(0, 1) remains True.

Implementation in Python, C++, and Java

The complete, runnable implementations below showcase a unified RollbackDSU featuring union-by-size, snapshot generation, LIFO stack rollbacks, and verification test drivers.

class RollbackDSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
        self.num_components = n
        self.history = []  # Stack of (u, old_parent_u, v, old_size_v)

    def find(self, u):
        # Strictly NO path compression to preserve LIFO rollback invariant
        curr = u
        while curr != self.parent[curr]:
            curr = self.parent[curr]
        return curr

    def connected(self, u, v):
        return self.find(u) == self.find(v)

    def union(self, u, v):
        root_u = self.find(u)
        root_v = self.find(v)

        if root_u == root_v:
            return False

        # Union by size: attach smaller tree under larger tree
        if self.size[root_u] > self.size[root_v]:
            root_u, root_v = root_v, root_u

        # Log state modification before mutation
        self.history.append((root_u, self.parent[root_u], root_v, self.size[root_v]))

        self.parent[root_u] = root_v
        self.size[root_v] += self.size[root_u]
        self.num_components -= 1
        return True

    def snapshot(self):
        return len(self.history)

    def rollback_to(self, checkpoint):
        while len(self.history) > checkpoint:
            root_u, old_parent_u, root_v, old_size_v = self.history.pop()
            self.parent[root_u] = old_parent_u
            self.size[root_v] = old_size_v
            self.num_components += 1


if __name__ == "__main__":
    dsu = RollbackDSU(5)
    print(f"Initial components: {dsu.num_components}")

    dsu.union(0, 1)
    dsu.union(2, 3)
    print("After union(0, 1) and union(2, 3):")
    print(f"Components: {dsu.num_components}")
    print(f"Connected(0, 1): {dsu.connected(0, 1)}, Connected(2, 3): {dsu.connected(2, 3)}")

    snap1 = dsu.snapshot()
    print(f"Saved Snapshot 1 (cp={snap1}).")

    dsu.union(1, 2)
    dsu.union(3, 4)
    print("After union(1, 2) and union(3, 4):")
    print(f"Components: {dsu.num_components}")
    print(f"Connected(0, 4): {dsu.connected(0, 4)}")

    print(f"Rolling back to Snapshot 1 (cp={snap1})...")
    dsu.rollback_to(snap1)
    print(f"Components: {dsu.num_components}")
    print(f"Connected(0, 4): {dsu.connected(0, 4)}")
    print(f"Connected(0, 1): {dsu.connected(0, 1)}, Connected(2, 3): {dsu.connected(2, 3)}")

    print("Rolling back to Snapshot 0 (cp=0)...")
    dsu.rollback_to(0)
    print(f"Components: {dsu.num_components}")
    print(f"Connected(0, 1): {dsu.connected(0, 1)}")

#include <iostream>
#include <vector>
#include <numeric>

class RollbackDSU {
    struct MutationFrame {
        int u;
        int old_parent_u;
        int v;
        int old_size_v;
    };

    std::vector<int> parent;
    std::vector<int> size;
    std::vector<MutationFrame> history;
    int num_components;

public:
    explicit RollbackDSU(int n) : parent(n), size(n, 1), num_components(n) {
        std::iota(parent.begin(), parent.end(), 0);
    }

    int find(int u) const {
        // Strictly NO path compression
        int curr = u;
        while (curr != parent[curr]) {
            curr = parent[curr];
        }
        return curr;
    }

    bool connected(int u, int v) const {
        return find(u) == find(v);
    }

    bool union_sets(int u, int v) {
        int root_u = find(u);
        int root_v = find(v);

        if (root_u == root_v) return false;

        if (size[root_u] > size[root_v]) {
            std::swap(root_u, root_v);
        }

        // Record history frame before write
        history.push_back({root_u, parent[root_u], root_v, size[root_v]});

        parent[root_u] = root_v;
        size[root_v] += size[root_u];
        num_components--;
        return true;
    }

    int snapshot() const {
        return static_cast<int>(history.size());
    }

    void rollback_to(int checkpoint) {
        while (static_cast<int>(history.size()) > checkpoint) {
            MutationFrame frame = history.back();
            history.pop_back();

            parent[frame.u] = frame.old_parent_u;
            size[frame.v] = frame.old_size_v;
            num_components++;
        }
    }

    int get_num_components() const {
        return num_components;
    }
};

int main() {
    RollbackDSU dsu(5);
    std::cout << "Initial components: " << dsu.get_num_components() << "\n";

    dsu.union_sets(0, 1);
    dsu.union_sets(2, 3);
    std::cout << "After union(0, 1) and union(2, 3):\n";
    std::cout << "Components: " << dsu.get_num_components() << "\n";
    std::cout << "Connected(0, 1): " << (dsu.connected(0, 1) ? "True" : "False")
              << ", Connected(2, 3): " << (dsu.connected(2, 3) ? "True" : "False") << "\n";

    int snap1 = dsu.snapshot();
    std::cout << "Saved Snapshot 1 (cp=" << snap1 << ").\n";

    dsu.union_sets(1, 2);
    dsu.union_sets(3, 4);
    std::cout << "After union(1, 2) and union(3, 4):\n";
    std::cout << "Components: " << dsu.get_num_components() << "\n";
    std::cout << "Connected(0, 4): " << (dsu.connected(0, 4) ? "True" : "False") << "\n";

    std::cout << "Rolling back to Snapshot 1 (cp=" << snap1 << ")...\n";
    dsu.rollback_to(snap1);
    std::cout << "Components: " << dsu.get_num_components() << "\n";
    std::cout << "Connected(0, 4): " << (dsu.connected(0, 4) ? "True" : "False") << "\n";
    std::cout << "Connected(0, 1): " << (dsu.connected(0, 1) ? "True" : "False")
              << ", Connected(2, 3): " << (dsu.connected(2, 3) ? "True" : "False") << "\n";

    std::cout << "Rolling back to Snapshot 0 (cp=0)...\n";
    dsu.rollback_to(0);
    std::cout << "Components: " << dsu.get_num_components() << "\n";
    std::cout << "Connected(0, 1): " << (dsu.connected(0, 1) ? "True" : "False") << "\n";

    return 0;
}

import java.util.ArrayDeque;
import java.util.Deque;

public class Main {

    public static class RollbackDSU {
        private static class MutationFrame {
            int u;
            int oldParentU;
            int v;
            int oldSizeV;

            MutationFrame(int u, int oldParentU, int v, int oldSizeV) {
                this.u = u;
                this.oldParentU = oldParentU;
                this.v = v;
                this.oldSizeV = oldSizeV;
            }
        }

        private final int[] parent;
        private final int[] size;
        private final Deque<MutationFrame> history = new ArrayDeque<>();
        private int numComponents;

        public RollbackDSU(int n) {
            this.parent = new int[n];
            this.size = new int[n];
            this.numComponents = n;
            for (int i = 0; i < n; i++) {
                parent[i] = i;
                size[i] = 1;
            }
        }

        public int find(int u) {
            // Strictly NO path compression
            int curr = u;
            while (curr != parent[curr]) {
                curr = parent[curr];
            }
            return curr;
        }

        public boolean connected(int u, int v) {
            return find(u) == find(v);
        }

        public boolean union(int u, int v) {
            int rootU = find(u);
            int rootV = find(v);

            if (rootU == rootV) return false;

            if (size[rootU] > size[rootV]) {
                int temp = rootU;
                rootU = rootV;
                rootV = temp;
            }

            // Log mutation frame
            history.push(new MutationFrame(rootU, parent[rootU], rootV, size[rootV]));

            parent[rootU] = rootV;
            size[rootV] += size[rootU];
            numComponents--;
            return true;
        }

        public int snapshot() {
            return history.size();
        }

        public void rollbackTo(int checkpoint) {
            while (history.size() > checkpoint) {
                MutationFrame frame = history.pop();
                parent[frame.u] = frame.oldParentU;
                size[frame.v] = frame.oldSizeV;
                numComponents++;
            }
        }

        public int getNumComponents() {
            return numComponents;
        }
    }

    public static void main(String[] args) {
        RollbackDSU dsu = new RollbackDSU(5);
        System.out.println("Initial components: " + dsu.getNumComponents());

        dsu.union(0, 1);
        dsu.union(2, 3);
        System.out.println("After union(0, 1) and union(2, 3):");
        System.out.println("Components: " + dsu.getNumComponents());
        System.out.println("Connected(0, 1): " + dsu.connected(0, 1) + ", Connected(2, 3): " + dsu.connected(2, 3));

        int snap1 = dsu.snapshot();
        System.out.println("Saved Snapshot 1 (cp=" + snap1 + ").");

        dsu.union(1, 2);
        dsu.union(3, 4);
        System.out.println("After union(1, 2) and union(3, 4):");
        System.out.println("Components: " + dsu.getNumComponents());
        System.out.println("Connected(0, 4): " + dsu.connected(0, 4));

        System.out.println("Rolling back to Snapshot 1 (cp=" + snap1 + ")...");
        dsu.rollbackTo(snap1);
        System.out.println("Components: " + dsu.getNumComponents());
        System.out.println("Connected(0, 4): " + dsu.connected(0, 4));
        System.out.println("Connected(0, 1): " + dsu.connected(0, 1) + ", Connected(2, 3): " + dsu.connected(2, 3));

        System.out.println("Rolling back to Snapshot 0 (cp=0)...");
        dsu.rollbackTo(0);
        System.out.println("Components: " + dsu.getNumComponents());
        System.out.println("Connected(0, 1): " + dsu.connected(0, 1));
    }
}

Complexity, Correctness, and Invariants

The theoretical guarantee of rollback structures relies on strict balance heuristics without query-driven mutations.

Technique / Approach	Find Time Complexity	Union Time Complexity	Rollback Cost per Op	Auxiliary Space Overhead	Support Branching History?
Rollback DSU (Union-by-Size)	$O(\log N)$	$O(\log N)$	$O(1)$ stack pop	$O(M)$ for $M$ operations	LIFO / Tree DFS order only
Standard DSU (Path Comp + Rank)	$O(\alpha(N))$ amortized	$O(\alpha(N))$ amortized	Impossible (queries corrupt stack)	$O(N)$ base arrays	None (destructive updates)
Fully Persistent DSU (Fat Nodes / Trees)	$O(\log N)$	$O(\log N)$	$O(1)$ pointer move	$O(M \log N)$ path copying	Full DAG / arbitrary version access
Rebuilding from Scratch	$O(\alpha(N))$	$O(\alpha(N))$	$O(M \cdot \alpha(N))$ full re-scan	$O(M)$ edge lists	Recomputes entire state from start

LIFO Execution Invariant: For any sequence of mutations $M_1, M_2, \dots, M_k$ applied to state $S_0$, popping stack frames in exact reverse order $M_k, M_{k-1}, \dots, M_{j+1}$ restores memory state $S_j$. Because union-by-size guarantees tree height $H \le \log_2 N$, queries remain strictly bounded in $O(\log N)$ worst-case time without needing path compression.

Variants, Pitfalls, and Optimizations

1. Offline Dynamic Connectivity (Divide & Conquer over Time)

The most prominent application of Rollback DSU is solving dynamic graph queries (edge additions, edge deletions, connected component queries) offline. By building a segment tree over time intervals $[0, T-1]$, each edge's existence duration is decomposed into $O(\log T)$ segment tree nodes. A DFS traversal over the segment tree applies edges on entry (union), answers leaf queries, and rolls back edges on exit (rollback).

2. The Path Compression Stack Poisoning Pitfall

Standard DSU uses path compression during find(u) to flatten tree paths to the root. However, path compression mutates $O(\log N)$ parent pointers during read operations. If these pointer modifications are pushed to the undo stack, read queries pollute the stack with $O(N)$ write noise, destroying both $O(1)$ rollback complexity and stack alignment.

Common Implementation Pitfalls:

Enabling Path Compression: Including parent[u] = find(parent[u]) inside a rollback structure causes queries to alter memory layout, filling the undo stack with $O(N)$ pointer writes and invalidating rollback checkpoints.
Mutating State Before Logging: Overwriting array cells before pushing old values to the undo stack causes the structure to record new values instead of old values, permanently corrupting memory during rollbacks.
Out-of-Order Rollbacks: Attempting to rollback to arbitrary historical versions rather than strictly LIFO checkpoints violates stack ordering. For non-LIFO versioning, use fully persistent data structures.

Practice Problems and Real-World Use

Rollback data structures are heavily utilized in offline competitive programming problems, constraint programming solvers, and transactional state engines.

Problem / System	Core Concept Applied	Difficulty
Codeforces 1140F - Extending Set of Points	Divide & Conquer segment tree over time combined with Rollback DSU.	Hard
Offline Dynamic Connectivity	Processing edge insertions, deletions, and component queries in $O(Q \log^2 Q)$ time.	Hard
SAT Solvers / CDCL Solvers	Rolling back variable assignments during backtracking search tree unwinding.	Real-World System
Database In-Memory Undo Logs	Reverting uncommitted transaction writes in transactional memory systems.	Real-World System
Codeforces 601D / Tree DFS Backtracking	Maintaining graph invariants during DFS tree traversals and subtree merging.	Very Hard
Gym 100551A - Connection	Managing edge presence intervals using segment tree time decomposition and Rollback DSU.	Hard

Cookie Consent