Implementing Persistent Data Structures

1. Applying Persistence Concept

Pattern	Description	Key Characteristics	Use Cases
Immutable Data Structures	Once created, data structures cannot be modified. Any "change" results in a new structure.	• No side effects • Thread-safe • Easy to reason about	• Functional programming • Concurrent systems • Version control systems
Structural Sharing	When a new version is created, it shares as much structure as possible with the previous version.	• Memory efficient • Fast operations • Reduced copying	• Trees and lists • Database systems • UI frameworks
Snapshotting	Creating a point-in-time copy of the data structure that can be referenced later.	• Time travel debugging • Undo/redo functionality • Audit trails	• State management in apps • Blockchain • Configuration systems

Example: Immutable List Implementation

const ImmutableList = (function() {
  const create = (items = []) => ({
    items,
    push: (value) => create([...items, value]),
    pop: () => create(items.slice(0, -1)),
    get: (index) => items[index],
    size: () => items.length
  });

  return { create };
})();

// Usage
let list = ImmutableList.create([1, 2, 3]);
let newList = list.push(4);
console.log(list.get(0)); // 1
console.log(newList.get(3)); // 4

Note: Structural sharing allows for efficient memory usage by reusing unchanged parts of the data structure when creating new versions.

2. Implementing Persistent Array

Operation	Description	Time Complexity	Space Complexity
get(index)	Retrieve element at index	O(log n)	O(1)
set(index, value)	Update element at index	O(log n)	O(log n)
size()	Return number of elements	O(1)	O(1)
append(value)	Add element to end	O(log n)	O(log n)

Example: Creating and Updating a Persistent Array

class PersistentArray {
  constructor(arr = []) {
    this.root = buildTree(arr);
    this.size = arr.length;
  }

  get(index) {
    return getValueAt(this.root, index);
  }

  set(index, value) {
    const newRoot = setValueAt(this.root, index, value);
    return new PersistentArray(getValuesFromTree(newRoot));
  }

  append(value) {
    const newRoot = setValueAt(this.root, this.size, value);
    return new PersistentArray(getValuesFromTree(newRoot));
  }
}

// Example usage:
const arr1 = new PersistentArray([1, 2, 3]);
const arr2 = arr1.set(1, 5); // Creates new array with [1, 5, 3]
const arr3 = arr2.append(4); // Creates new array with [1, 5, 3, 4]

console.log(arr1.get(1)); // 2
console.log(arr2.get(1)); // 5
console.log(arr3.get(3)); // 4

Note: The implementation uses a tree structure to maintain versions. Each update creates a new version while sharing unchanged parts of the tree.

3. Implementing Persistent Stack

Operation	Description	Time Complexity	Space Complexity
push(value)	Creates a new stack with the value added to the top	O(1)	O(h)
pop()	Creates a new stack with the top element removed	O(1)	O(h)
top()	Returns the top element without modifying the stack	O(1)	O(1)
isEmpty()	Checks if the stack is empty	O(1)	O(1)

Example: Persistent Stack Implementation

class PersistentStack {
  constructor(elements = []) {
    this.elements = elements;
  }

  push(value) {
    return new PersistentStack([...this.elements, value]);
  }

  pop() {
    if (this.elements.length === 0) return this;
    const newElements = [...this.elements];
    newElements.pop();
    return new PersistentStack(newElements);
  }

  top() {
    return this.elements.length > 0 ? this.elements[this.elements.length - 1] : null;
  }

  isEmpty() {
    return this.elements.length === 0;
  }
}

// Usage example
const stack1 = new PersistentStack([1, 2, 3]);
const stack2 = stack1.push(4); // New stack with 4 on top
const stack3 = stack2.pop();   // New stack with 4 removed

console.log(stack1.top()); // 3
console.log(stack2.top()); // 4
console.log(stack3.top()); // 3

Note: The persistent stack implementation uses structural sharing to maintain previous versions of the stack, allowing efficient memory usage and immutability.

4. Implementing Persistent Segment Tree

A persistent segment tree allows queries and updates to be made while maintaining previous versions of the data structure. Each update creates a new version, enabling efficient historical queries.

Operation	Description	Time Complexity	Space Complexity
Build	Constructs a persistent segment tree from an array of size n	O(n)	O(n log n)
Query	Retrieves the value in a range [l, r]	O(log n)	O(1)
Update	Updates a value at index i and returns new version	O(log n)	O(log n)

Example: Building a Persistent Segment Tree

class PersistentSegmentTree {
  constructor(arr) {
    this.n = arr.length;
    this.version = 0;
    this.tree = [this.buildTree(arr)];
  }

  buildTree(arr) {
    const tree = new Array(4 * this.n);
    this.buildUtil(arr, tree, 0, this.n - 1, 0);
    return tree;
  }

  buildUtil(arr, tree, ss, se, si) {
    if (ss === se) {
      tree[si] = arr[ss];
      return;
    }
    const mid = (ss + se) / 2;
    this.buildUtil(arr, tree, ss, mid, 2 * si + 1);
    this.buildUtil(arr, tree, mid + 1, se, 2 * si + 2);
    tree[si] = tree[2 * si + 1] + tree[2 * si + 2];
  }

  query(tree, ss, se, qs, qe) {
    if (qs > se || qe < ss) return 0;
    if (qs <= ss && qe >= se) return tree[si];
    const mid = (ss + se) / 2;
    return this.query(tree, ss, mid, qs, qe) +
           this.query(tree, mid + 1, se, qs, qe);
  }

  update(tree, ss, se, i, diff) {
    if (i < ss || i > se) return;
    tree[si] += diff;
    if (ss !== se) {
      const mid = (ss + se) / 2;
      this.update(tree, ss, mid, i, diff);
      this.update(tree, mid + 1, se, i, diff);
    }
  }

  // Returns new version of the tree
  updateVersion(arr, i, val) {
    const newTree = [...this.tree[this.version]];
    const diff = val - arr[i];
    this.update(newTree, 0, this.n - 1, i, diff);
    this.version++;
    this.tree.push(newTree);
    return newTree;
  }
}

Note: In a persistent segment tree, each update operation creates a new version of the tree. This is useful for scenarios where historical queries are required, such as in version-controlled systems or debugging tools.

5. Implementing Persistent Trie

Operation	Description	Time Complexity	Space Complexity
insert(key, value)	Inserts a new key-value pair into the trie	O(m)	O(m)
search(key)	Retrieves the value associated with a key	O(m)	O(1)
delete(key)	Deletes a key-value pair from the trie	O(m)	O(m)

Example: Inserting into a Persistent Trie

class TrieNode {
  constructor() {
    this.children = new Map();
    this.value = null;
  }
}

class PersistentTrie {
  constructor() {
    this.root = new TrieNode();
  }

  insert(key, value) {
    const newRoot = this._insertRecursive(this.root, key, 0, value);
    return new PersistentTrie(newRoot);
  }

  _insertRecursive(node, key, index, value) {
    if (index === key.length) {
      const newNode = new TrieNode();
      newNode.value = value;
      return newNode;
    }

    const char = key[index];
    const newChildren = new Map(node.children);
    const childNode = node.children.get(char);

    if (childNode) {
      newChildren.set(char, this._insertRecursive(childNode, key, index + 1, value));
    } else {
      newChildren.set(char, this._insertRecursive(new TrieNode(), key, index + 1, value));
    }

    const newNode = new TrieNode();
    newNode.children = newChildren;
    return newNode;
  }
}

const trie = new PersistentTrie();
const updatedTrie = trie.insert("hello", "world");

Example: Searching in a Persistent Trie

class PersistentTrie {
  search(key) {
    return this._searchRecursive(this.root, key, 0);
  }

  _searchRecursive(node, key, index) {
    if (index === key.length) {
      return node.value;
    }

    const char = key[index];
    const childNode = node.children.get(char);

    if (!childNode) {
      return null;
    }

    return this._searchRecursive(childNode, key, index + 1);
  }
}

const trie = new PersistentTrie();
trie.insert("hello", "world");
console.log(trie.search("hello")); // Output: "world"

Note: In a persistent trie, each operation returns a new trie instance, preserving the previous state.

6. Solving Range Queries

Operation	Description	Time Complexity	Space Complexity
Range Sum Query (RSQ)	Computes sum of elements in a given range [l, r]	O(1) with preprocessing	O(n)
Range Minimum Query (RMQ)	Finds minimum element in a given range [l, r]	O(1) with preprocessing	O(n)
Range Maximum Query (RMQ)	Finds maximum element in a given range [l, r]	O(1) with preprocessing	O(n)

Example: Segment Tree for Range Sum Query

class SegmentTree {
  constructor(arr) {
    this.n = arr.length;
    this.tree = new Array(4 * this.n).fill(0);
    this.build(arr, 0, 0, this.n - 1);
  }

  build(arr, node, start, end) {
    if (start === end) {
      this.tree[node] = arr[start];
    } else {
      const mid = Math.floor((start + end) / 2);
      this.build(arr, 2 * node + 1, start, mid);
      this.build(arr, 2 * node + 2, mid + 1, end);
      this.tree[node] = this.tree[2 * node + 1] + this.tree[2 * node + 2];
    }
  }

  query(node, start, end, l, r) {
    if (r < start || end < l) return 0;
    if (l <= start && end <= r) return this.tree[node];

    const mid = Math.floor((start + end) / 2);
    return this.query(2 * node + 1, start, mid, l, r) +
           this.query(2 * node + 2, mid + 1, end, l, r);
  }

  sum(l, r) {
    return this.query(0, 0, this.n - 1, l, r);
  }
}

const arr = [1, 3, 5, 7, 9, 11];
const segTree = new SegmentTree(arr);
console.log(segTree.sum(1, 3)); // Output: 15 (3 + 5 + 7)

Example: Binary Indexed Tree (Fenwick Tree) for Range Sum

class BIT {
  constructor(size) {
    this.size = size;
    this.tree = new Array(size + 1).fill(0);
  }

  update(index, delta) {
    for (let i = index; i <= this.size; i += i & (-i)) {
      this.tree[i] += delta;
    }
  }

  prefixSum(index) {
    let sum = 0;
    for (let i = index; i > 0; i -= i & (-i)) {
      sum += this.tree[i];
    }
    return sum;
  }

  rangeSum(l, r) {
    return this.prefixSum(r) - this.prefixSum(l - 1);
  }
}

const bit = new BIT(6);
const arr = [1, 3, 5, 7, 9, 11];
for (let i = 0; i < arr.length; i++) {
  bit.update(i + 1, arr[i]);
}
console.log(bit.rangeSum(2, 4)); // Output: 15 (3 + 5 + 7)

Note: Segment trees are more flexible for dynamic updates, while Fenwick trees offer better space efficiency and faster constant factors for prefix sums.

7. Implementing Copy-on-Write

Operation	Description	Implementation	Notes
copyOnWrite	Creates a new version of the data structure with modifications	`const original = [1, 2, 3]; const modified = [...original, 4]; // New array with added element`	Original remains unchanged; new structure created
immutableUpdate	Updates a value in an immutable structure without mutation	`const obj = { a: 1, b: 2 }; const updated = { ...obj, b: 3 }; // New object with updated value`	Use spread operator or functional update methods

Example: Copy-on-Write in a Tree

class ImmutableTree {
  constructor(value, left = null, right = null) {
    this.value = value;
    this.left = left;
    this.right = right;
  }

  withValue(newValue) {
    return new ImmutableTree(newValue, this.left, this.right);
  }

  withLeft(newLeft) {
    return new ImmutableTree(this.value, newLeft, this.right);
  }
}

const tree = new ImmutableTree(10, new ImmutableTree(5), new ImmutableTree(15));
const updated = tree.withValue(20); // Creates new tree with value 20

Note: Copy-on-Write ensures data immutability by creating new structures when changes are made, preserving the original state.

8. Managing Version History

Operation	Description	Time Complexity	Space Complexity
createSnapshot()	Creates a new version of the data structure with current state	O(1)	O(1) for reference, O(n) for full copy
revertToVersion(versionId)	Restores the structure to a previous version	O(log n)	O(1) if using path copying
getVersionInfo(versionId)	Retrieves metadata about a specific version	O(1)	O(1)

Example: Creating and Reverting Snapshots

class ImmutableArray {
  constructor(data = []) {
    this.version = 0;
    this.data = data;
    this.snapshots = new Map();
  }

  createSnapshot() {
    const versionId = ++this.version;
    this.snapshots.set(versionId, { data: this.data, version: versionId });
    return versionId;
  }

  revertToVersion(versionId) {
    const snapshot = this.snapshots.get(versionId);
    if (snapshot) {
      this.data = snapshot.data;
      this.version = versionId;
    }
  }

  push(value) {
    const newData = [...this.data, value];
    this.data = newData;
    return this;
  }
}

const arr = new ImmutableArray([1, 2, 3]);
const snap1 = arr.createSnapshot(); // version 1
arr.push(4);
const snap2 = arr.createSnapshot(); // version 2

console.log(arr.data); // [1, 2, 3, 4]
arr.revertToVersion(snap1);
console.log(arr.data); // [1, 2, 3]

Note: Version history management in persistent data structures often involves maintaining a log or map of versions to allow for efficient rollback and inspection.

9. Optimizing Space Usage

Technique	Description	Space Complexity	Notes
Path Copying	Creates new paths for modified nodes while reusing unchanged parts of the tree.	O(log n)	Reduces memory overhead by sharing immutable nodes
Node Sharing	Reuses nodes that are not modified in new versions of the data structure.	O(1) per shared node	Enables efficient version control and rollback
Lazy Evaluation	Defers computation until necessary, avoiding unnecessary node creation.	O(1) for lazy nodes	Improves performance by reducing redundant operations
Garbage Collection	Removes old versions of data structures when no longer referenced.	O(n) for cleanup	Prevents memory leaks in long-lived applications

Example: Path Copying in a Persistent List

class PersistentList {
  constructor(elements = []) {
    this.root = this.buildTree(elements);
  }

  buildTree(elements) {
    if (elements.length === 0) return null;
    const mid = Math.floor(elements.length / 2);
    return {
      value: elements[mid],
      left: this.buildTree(elements.slice(0, mid)),
      right: this.buildTree(elements.slice(mid + 1))
    };
  }

  append(value) {
    const newRoot = this.copyAndAppend(this.root, value);
    return new PersistentList(this.toList(newRoot));
  }

  copyAndAppend(node, value) {
    if (!node) return { value, left: null, right: null };
    // Reuse existing nodes where possible
    return {
      value: node.value,
      left: this.copyAndAppend(node.left, value),
      right: node.right
    };
  }

  toList(node) {
    if (!node) return [];
    return [...this.toList(node.left), node.value, ...this.toList(node.right)];
  }
}

Note: Path copying ensures that only the necessary nodes are duplicated, minimizing space usage while maintaining immutability.

10. Applying to Undo Operations

Operation	Description	Time Complexity	Space Complexity
Undo	Reverts to the previous state of the data structure	O(1)	O(1)
Redo	Reapplies the last undone operation	O(1)	O(1)
Save State	Creates a snapshot of the current state	O(1)	O(1)

Example: Undo Stack Implementation

class UndoStack {
  constructor() {
    this.stack = [];
    this.history = [];
  }

  push(value) {
    this.stack.push(value);
    this.history.push([...this.stack]);
  }

  pop() {
    if (this.stack.length === 0) return null;
    this.history.pop();
    return this.stack.pop();
  }

  undo() {
    if (this.history.length > 1) {
      this.stack = [...this.history[this.history.length - 2]];
      this.history.pop();
    }
  }

  redo() {
    if (this.history.length > 1) {
      this.stack = [...this.history[this.history.length - 1]];
    }
  }
}

const stack = new UndoStack();
stack.push(1);
stack.push(2);
stack.undo(); // Stack becomes [1]
stack.redo(); // Stack becomes [1, 2]

Note: The history array stores snapshots of the stack at each operation to support undo/redo.