Skip to main content

Augmenting Data Structures

Introduction to Augmentation​

Augmenting data structures involves extending basic data structures with additional information to support operations that would otherwise be inefficient or impossible. This powerful technique allows us to:

  1. Enhance standard data structures for specialized operations
  2. Reduce time complexity for specific use cases
  3. Create composite structures that combine benefits of multiple structures
  4. Support complex queries while maintaining efficient updates

Let's explore several important augmented data structures and their applications.

Order Statistics Trees​

Concept and Purpose​

Order statistics trees extend binary search trees by maintaining the size of each subtree, allowing for rank-based queries.

Implementation​

class OSTreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
    this.size = 1; // Includes itself
  }
}

class OrderStatisticTree {
  constructor() {
    this.root = null;
  }
  
  // Get size of a node (0 if null)
  size(node) {
    return node ? node.size : 0;
  }
  
  // Insert a value with size maintenance
  insert(value) {
    this.root = this._insertRecursive(this.root, value);
  }
  
  _insertRecursive(node, value) {
    if (!node) {
      return new OSTreeNode(value);
    }
    
    if (value < node.value) {
      node.left = this._insertRecursive(node.left, value);
    } else if (value > node.value) {
      node.right = this._insertRecursive(node.right, value);
    }
    
    // Update size after insertion
    node.size = 1 + this.size(node.left) + this.size(node.right);
    return node;
  }
  
  // Find the kth smallest element (1-indexed)
  select(k) {
    if (k < 1 || k > this.size(this.root)) {
      return null;
    }
    return this._selectRecursive(this.root, k);
  }
  
  _selectRecursive(node, k) {
    if (!node) return null;
    
    const leftSize = this.size(node.left);
    
    // If k equals the size of left subtree + 1, the current node is the answer
    if (leftSize + 1 === k) {
      return node.value;
    }
    
    // If k is less than size of left subtree + 1, search in left subtree
    if (k <= leftSize) {
      return this._selectRecursive(node.left, k);
    }
    
    // Otherwise, search in right subtree
    // Adjust k to account for skipping left subtree and current node
    return this._selectRecursive(node.right, k - leftSize - 1);
  }
  
  // Find rank of a given value (how many elements are <= value)
  rank(value) {
    return this._rankRecursive(this.root, value);
  }
  
  _rankRecursive(node, value) {
    if (!node) return 0;
    
    if (value < node.value) {
      return this._rankRecursive(node.left, value);
    } else if (value > node.value) {
      return 1 + this.size(node.left) + this._rankRecursive(node.right, value);
    } else {
      return this.size(node.left) + 1; // Value equals node's value
    }
  }
}

// Usage example
const osTree = new OrderStatisticTree();
[5, 2, 8, 1, 3, 7, 9, 4, 6].forEach(val => osTree.insert(val));

console.log(osTree.select(4)); // 4th smallest element: 4
console.log(osTree.rank(6));   // Rank of 6: 6 (because 1,2,3,4,5,6 are <= 6)

Applications​

  1. Finding the median in a dynamic set
  2. Determining the kth order statistic
  3. Computing rank of elements
  4. Maintaining sorted sequences with frequent queries

Interval Trees​

Concept and Purpose​

Interval trees are augmented red-black trees that store intervals and can efficiently find all intervals that overlap with a given query interval.

Implementation​

class IntervalNode {
  constructor(low, high) {
    this.interval = { low, high };
    this.max = high;  // Maximum endpoint in the subtree
    this.left = null;
    this.right = null;
    this.color = "RED"; // For red-black tree balancing
  }
}

class IntervalTree {
  constructor() {
    this.NIL = new IntervalNode(null, null);
    this.NIL.color = "BLACK";
    this.NIL.left = null;
    this.NIL.right = null;
    this.root = this.NIL;
  }
  
  // Update max value for a node based on its children
  updateMax(node) {
    if (node === this.NIL) return;
    
    let maxVal = node.interval.high;
    if (node.left !== this.NIL) {
      maxVal = Math.max(maxVal, node.left.max);
    }
    if (node.right !== this.NIL) {
      maxVal = Math.max(maxVal, node.right.max);
    }
    node.max = maxVal;
  }
  
  // Insert a new interval [low, high]
  insert(low, high) {
    const newNode = new IntervalNode(low, high);
    newNode.left = this.NIL;
    newNode.right = this.NIL;
    
    let y = this.NIL;
    let x = this.root;
    
    // Find the position to insert
    while (x !== this.NIL) {
      y = x;
      
      // Update max as we traverse down
      x.max = Math.max(x.max, high);
      
      if (low < x.interval.low) {
        x = x.left;
      } else {
        x = x.right;
      }
    }
    
    newNode.parent = y;
    
    if (y === this.NIL) {
      this.root = newNode; // Tree was empty
    } else if (low < y.interval.low) {
      y.left = newNode;
    } else {
      y.right = newNode;
    }
    
    // Update max values up the tree
    while (y !== this.NIL) {
      this.updateMax(y);
      y = y.parent;
    }
    
    // Balance the tree (simplified, in practice would use red-black tree balancing)
    this.balanceAfterInsertion(newNode);
  }
  
  // Simplified red-black tree balancing
  balanceAfterInsertion(node) {
    // This would contain the standard red-black tree balancing operations
    // For brevity, implementation is omitted
  }
  
  // Find all intervals that overlap with [low, high]
  findOverlappingIntervals(low, high) {
    const result = [];
    this._findOverlappingRecursive(this.root, low, high, result);
    return result;
  }
  
  _findOverlappingRecursive(node, low, high, result) {
    if (node === this.NIL) return;
    
    // If current node's max is less than query low, no overlaps possible in this subtree
    if (node.max < low) return;
    
    // Check left subtree
    if (node.left !== this.NIL) {
      this._findOverlappingRecursive(node.left, low, high, result);
    }
    
    // Check if current interval overlaps with query
    if (this.overlaps(node.interval, { low, high })) {
      result.push(node.interval);
    }
    
    // If current low is greater than query high, no need to check right subtree
    if (node.interval.low > high) return;
    
    // Check right subtree
    if (node.right !== this.NIL) {
      this._findOverlappingRecursive(node.right, low, high, result);
    }
  }
  
  // Check if two intervals overlap
  overlaps(a, b) {
    return a.low <= b.high && b.low <= a.high;
  }
}

// Usage example
const intervalTree = new IntervalTree();
intervalTree.insert(15, 20);
intervalTree.insert(10, 30);
intervalTree.insert(17, 19);
intervalTree.insert(5, 20);
intervalTree.insert(12, 15);

console.log(intervalTree.findOverlappingIntervals(14, 16));
// Expected output: intervals containing [14, 16], such as [10, 30], [15, 20], etc.

Applications​

  1. Calendar applications to find overlapping events
  2. Database systems for range queries
  3. Computational geometry for line segment intersection
  4. Network analysis for overlapping time periods

Segment Trees​

Concept and Purpose​

Segment trees are versatile data structures that can efficiently answer range queries and support range updates on arrays.

Implementation​

class SegmentTree {
  constructor(array) {
    this.array = array;
    this.tree = new Array(4 * array.length).fill(0);
    this.build(0, 0, array.length - 1);
  }
  
  // Build the segment tree
  build(node, start, end) {
    if (start === end) {
      this.tree[node] = this.array[start];
      return;
    }
    
    const mid = Math.floor((start + end) / 2);
    
    // Recursively build left and right subtrees
    this.build(2 * node + 1, start, mid);
    this.build(2 * node + 2, mid + 1, end);
    
    // Internal node stores sum of both children
    this.tree[node] = this.tree[2 * node + 1] + this.tree[2 * node + 2];
  }
  
  // Query the sum in range [l, r]
  querySum(l, r) {
    return this._querySumRecursive(0, 0, this.array.length - 1, l, r);
  }
  
  _querySumRecursive(node, start, end, l, r) {
    // No overlap with query range
    if (end < l || start > r) return 0;
    
    // Current segment is completely within query range
    if (start >= l && end <= r) return this.tree[node];
    
    // Partial overlap, query both children
    const mid = Math.floor((start + end) / 2);
    const leftSum = this._querySumRecursive(2 * node + 1, start, mid, l, r);
    const rightSum = this._querySumRecursive(2 * node + 2, mid + 1, end, l, r);
    
    return leftSum + rightSum;
  }
  
  // Update a single element
  update(index, newValue) {
    const diff = newValue - this.array[index];
    this.array[index] = newValue;
    
    this._updateRecursive(0, 0, this.array.length - 1, index, diff);
  }
  
  _updateRecursive(node, start, end, index, diff) {
    // Index is out of range
    if (index < start || index > end) return;
    
    // Update current node
    this.tree[node] += diff;
    
    if (start !== end) {
      const mid = Math.floor((start + end) / 2);
      this._updateRecursive(2 * node + 1, start, mid, index, diff);
      this._updateRecursive(2 * node + 2, mid + 1, end, index, diff);
    }
  }
  
  // Range update with lazy propagation (add val to all elements in range [l, r])
  // For brevity, lazy propagation implementation is simplified
  rangeUpdate(l, r, val) {
    this._rangeUpdateRecursive(0, 0, this.array.length - 1, l, r, val);
    
    // Update the original array to reflect changes
    for (let i = l; i <= r; i++) {
      this.array[i] += val;
    }
  }
  
  _rangeUpdateRecursive(node, start, end, l, r, val) {
    // No overlap
    if (end < l || start > r) return;
    
    // Complete overlap
    if (start >= l && end <= r) {
      this.tree[node] += val * (end - start + 1);
      // In a full implementation, we would set lazy values here
      return;
    }
    
    // Partial overlap
    const mid = Math.floor((start + end) / 2);
    this._rangeUpdateRecursive(2 * node + 1, start, mid, l, r, val);
    this._rangeUpdateRecursive(2 * node + 2, mid + 1, end, l, r, val);
    
    // Update current node based on children
    this.tree[node] = this.tree[2 * node + 1] + this.tree[2 * node + 2];
  }
}

// Usage example
const arr = [1, 3, 5, 7, 9, 11];
const segTree = new SegmentTree(arr);

console.log(segTree.querySum(1, 3)); // Sum of elements at indices 1,2,3: 3+5+7=15
segTree.update(2, 10); // Change value at index 2 from 5 to 10
console.log(segTree.querySum(1, 3)); // New sum: 3+10+7=20
segTree.rangeUpdate(0, 2, 5); // Add 5 to each element in range [0,2]
console.log(segTree.querySum(0, 5)); // Sum of all elements after updates

Applications​

  1. Range sum queries with updates
  2. Range minimum/maximum queries
  3. Finding frequency of elements in ranges
  4. Database systems for aggregation over ranges

Fenwick Trees (Binary Indexed Trees)​

Concept and Purpose​

Fenwick trees, also known as Binary Indexed Trees (BIT), provide an efficient way to maintain cumulative frequencies and perform prefix sum calculations.

Implementation​

class FenwickTree {
  constructor(size) {
    this.size = size;
    this.tree = new Array(size + 1).fill(0);
  }
  
  // Return sum of elements from index 1 to index
  getSum(index) {
    let sum = 0;
    index++; // Convert to 1-based indexing
    
    while (index > 0) {
      sum += this.tree[index];
      // Move to parent by removing least significant bit
      index -= index & -index;
    }
    
    return sum;
  }
  
  // Get sum in range [left, right], 0-based
  getSumRange(left, right) {
    return this.getSum(right) - (left > 0 ? this.getSum(left - 1) : 0);
  }
  
  // Add val to element at index
  update(index, val) {
    index++; // Convert to 1-based indexing
    
    while (index <= this.size) {
      this.tree[index] += val;
      // Move to next responsible index by adding least significant bit
      index += index & -index;
    }
  }
  
  // Construct from array
  static fromArray(arr) {
    const bit = new FenwickTree(arr.length);
    for (let i = 0; i < arr.length; i++) {
      bit.update(i, arr[i]);
    }
    return bit;
  }
}

// Usage example
const arr = [3, 2, 5, 1, 7, 9];
const bit = FenwickTree.fromArray(arr);

console.log(bit.getSum(3)); // Sum of elements at indices 0,1,2,3: 3+2+5+1=11
console.log(bit.getSumRange(1, 4)); // Sum of elements at indices 1,2,3,4: 2+5+1+7=15
bit.update(2, 3); // Add 3 to element at index 2 (5 becomes 8)
console.log(bit.getSumRange(1, 4)); // New sum: 2+8+1+7=18

Applications​

  1. Efficient prefix sums with updates
  2. Counting inversions in an array
  3. Implementation of range frequency queries
  4. Computing cumulative distribution functions

Sparse Tables​

Concept and Purpose​

Sparse tables provide efficient solutions to range queries on static arrays, particularly for idempotent operations like min, max, and gcd.

Implementation​

class SparseTable {
  constructor(arr, operation = Math.min) {
    this.array = arr;
    this.n = arr.length;
    this.operation = operation;
    
    // Calculate log table size
    this.logN = Math.floor(Math.log2(this.n)) + 1;
    
    // Initialize sparse table [i][j] where i is the index and j is the power of 2
    this.table = Array(this.n).fill().map(() => Array(this.logN).fill(0));
    
    this.build();
  }
  
  build() {
    // Fill in base cases (ranges of size 2^0 = 1)
    for (let i = 0; i < this.n; i++) {
      this.table[i][0] = this.array[i];
    }
    
    // Fill larger ranges
    for (let j = 1; j < this.logN; j++) {
      for (let i = 0; i + (1 << j) - 1 < this.n; i++) {
        this.table[i][j] = this.operation(
          this.table[i][j-1],
          this.table[i + (1 << (j-1))][j-1]
        );
      }
    }
  }
  
  // Query for min/max/gcd in range [left, right], 0-based
  query(left, right) {
    // For non-idempotent operations like sum, this method would need to be modified
    const length = right - left + 1;
    const k = Math.floor(Math.log2(length));
    
    return this.operation(
      this.table[left][k],
      this.table[right - (1 << k) + 1][k]
    );
  }
}

// Usage example
const arr = [4, 2, 3, 7, 1, 5, 3, 8];
const minTable = new SparseTable(arr);
const maxTable = new SparseTable(arr, Math.max);

console.log(minTable.query(1, 5)); // Min in range [1,5]: 1
console.log(maxTable.query(1, 5)); // Max in range [1,5]: 7

// Example with GCD operation
const gcd = (a, b) => b === 0 ? a : gcd(b, a % b);
const gcdArr = [2, 4, 6, 8, 12, 16];
const gcdTable = new SparseTable(gcdArr, gcd);
console.log(gcdTable.query(2, 5)); // GCD of elements at indices 2,3,4,5: gcd(6,8,12,16) = 2

Applications​

  1. Range minimum/maximum queries
  2. Longest Common Prefix (LCP) calculations
  3. GCD range queries
  4. Idempotent operations over large static datasets

Trie (Prefix Tree)​

Concept and Purpose​

Tries are tree-like data structures optimized for string operations, particularly for storing and searching collections of strings with common prefixes.

Implementation​

class TrieNode {
  constructor() {
    this.children = new Map();
    this.isEndOfWord = false;
    this.count = 0; // Count of words with this prefix
  }
}

class Trie {
  constructor() {
    this.root = new TrieNode();
  }
  
  // Insert a word into the trie
  insert(word) {
    let current = this.root;
    
    for (let i = 0; i < word.length; i++) {
      const char = word[i];
      if (!current.children.has(char)) {
        current.children.set(char, new TrieNode());
      }
      current = current.children.get(char);
      current.count++;
    }
    
    current.isEndOfWord = true;
  }
  
  // Search for a word in the trie
  search(word) {
    let current = this.root;
    
    for (let i = 0; i < word.length; i++) {
      const char = word[i];
      if (!current.children.has(char)) {
        return false;
      }
      current = current.children.get(char);
    }
    
    return current.isEndOfWord;
  }
  
  // Check if there is a word with the given prefix
  startsWith(prefix) {
    let current = this.root;
    
    for (let i = 0; i < prefix.length; i++) {
      const char = prefix[i];
      if (!current.children.has(char)) {
        return false;
      }
      current = current.children.get(char);
    }
    
    return true;
  }
  
  // Count words with the given prefix
  countWordsWithPrefix(prefix) {
    let current = this.root;
    
    for (let i = 0; i < prefix.length; i++) {
      const char = prefix[i];
      if (!current.children.has(char)) {
        return 0;
      }
      current = current.children.get(char);
    }
    
    return current.count;
  }
  
  // Delete a word from the trie
  delete(word) {
    this._deleteRecursive(this.root, word, 0);
  }
  
  _deleteRecursive(current, word, index) {
    // Base case: end of word
    if (index === word.length) {
      if (!current.isEndOfWord) {
        return false; // Word not found
      }
      
      current.isEndOfWord = false;
      return current.children.size === 0;
    }
    
    const char = word[index];
    if (!current.children.has(char)) {
      return false; // Word not found
    }
    
    const shouldDeleteNode = this._deleteRecursive(
      current.children.get(char),
      word,
      index + 1
    );
    
    if (shouldDeleteNode) {
      current.children.delete(char);
      current.count--;
      return current.children.size === 0 && !current.isEndOfWord;
    }
    
    current.count--;
    return false;
  }
}

// Usage example
const trie = new Trie();
["apple", "app", "apricot", "banana", "bat"].forEach(word => trie.insert(word));

console.log(trie.search("apple")); // true
console.log(trie.search("app")); // true
console.log(trie.search("appl")); // false
console.log(trie.startsWith("ap")); // true
console.log(trie.countWordsWithPrefix("ap")); // 3 (apple, app, apricot)
trie.delete("apple");
console.log(trie.search("apple")); // false
console.log(trie.countWordsWithPrefix("ap")); // 2 (app, apricot)

Applications​

  1. Autocomplete and spell checking
  2. IP routing tables
  3. T9 predictive text
  4. Longest prefix matching
  5. Full-text search indexing

Suffix Trees and Arrays​

Concept and Purpose​

Suffix trees and suffix arrays are powerful data structures for string processing, enabling efficient pattern matching and substring operations.

Suffix Array Implementation​

class SuffixArray {
  constructor(text) {
    this.text = text;
    this.n = text.length;
    this.suffixArray = this.buildSuffixArray();
    this.lcpArray = this.buildLCPArray();
  }
  
  // Build suffix array using a simplified approach
  // In practice, more efficient algorithms like SA-IS would be used
  buildSuffixArray() {
    // Create array of suffix objects with their starting positions
    const suffixes = Array(this.n)
      .fill()
      .map((_, i) => ({
        index: i,
        suffix: this.text.substring(i)
      }));
    
    // Sort suffixes lexicographically
    suffixes.sort((a, b) => a.suffix.localeCompare(b.suffix));
    
    // Extract indices to form the suffix array
    return suffixes.map(suffix => suffix.index);
  }
  
  // Build LCP (Longest Common Prefix) array
  buildLCPArray() {
    const lcp = Array(this.n).fill(0);
    
    // Inverse suffix array
    const rank = Array(this.n).fill(0);
    for (let i = 0; i < this.n; i++) {
      rank[this.suffixArray[i]] = i;
    }
    
    // Compute LCP values
    let h = 0; // LCP height
    for (let i = 0; i < this.n; i++) {
      if (rank[i] > 0) {
        const j = this.suffixArray[rank[i] - 1]; // Previous suffix in SA
        
        // Calculate LCP between suffixes at i and j
        while (i + h < this.n && j + h < this.n && 
               this.text[i + h] === this.text[j + h]) {
          h++;
        }
        
        lcp[rank[i]] = h;
        
        // Update h for next iteration
        if (h > 0) h--;
      }
    }
    
    return lcp;
  }
  
  // Search for a pattern using binary search on suffix array
  search(pattern) {
    const m = pattern.length;
    let left = 0;
    let right = this.n - 1;
    
    // Binary search for the lower bound
    while (left <= right) {
      const mid = Math.floor((left + right) / 2);
      const suffix = this.text.substring(this.suffixArray[mid]);
      const cmp = pattern.localeCompare(suffix.substring(0, m));
      
      if (cmp > 0) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
    
    const lowerBound = left;
    
    // If pattern not found
    if (lowerBound >= this.n || 
        !this.text.substring(this.suffixArray[lowerBound], this.suffixArray[lowerBound] + m) === pattern) {
      return [];
    }
    
    // Find upper bound
    right = this.n - 1;
    while (left <= right) {
      const mid = Math.floor((left + right) / 2);
      const suffix = this.text.substring(this.suffixArray[mid]);
      
      if (suffix.substring(0, m) === pattern) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
    
    const upperBound = right;
    
    // Return all matching positions
    const matches = [];
    for (let i = lowerBound; i <= upperBound; i++) {
      matches.push(this.suffixArray[i]);
    }
    
    return matches;
  }
  
  // Find the longest repeated substring
  longestRepeatedSubstring() {
    let maxLen = 0;
    let maxIndex = 0;
    
    for (let i = 1; i < this.n; i++) {
      if (this.lcpArray[i] > maxLen) {
        maxLen = this.lcpArray[i];
        maxIndex = i;
      }
    }
    
    if (maxLen === 0) return ""; // No repeated substring
    
    return this.text.substring(this.suffixArray[maxIndex], this.suffixArray[maxIndex] + maxLen);
  }
}

// Usage example
const text = "banana";
const sa = new SuffixArray(text);

console.log("Suffix Array:", sa.suffixArray); // [5, 3, 1, 0, 4, 2]
console.log("LCP Array:", sa.lcpArray); // [0, 1, 3, 0, 0, 2]
console.log("Positions of 'ana':", sa.search("ana")); // [1, 3]
console.log("Longest repeated substring:", sa.longestRepeatedSubstring()); // "ana"

Applications​

  1. String matching and pattern searching
  2. Genome sequence analysis
  3. Text compression
  4. Longest common substring
  5. Plagiarism detection

Advanced Implementations: Bloom Filters​

Concept and Purpose​

Bloom filters are space-efficient probabilistic data structures used to test whether an element is a member of a set, with a possibility of false positives but no false negatives.

Implementation​

class BloomFilter {
  constructor(size, hashFunctions) {
    this.size = size;
    this.hashFunctions = hashFunctions;
    this.bits = new Array(size).fill(false);
  }
  
  // Add an element to the filter
  add(element) {
    for (const hashFunc of this.hashFunctions) {
      const hash = hashFunc(element) % this.size;
      this.bits[hash] = true;
    }
  }
  
  // Test if an element might be in the set
  contains(element) {
    for (const hashFunc of this.hashFunctions) {
      const hash = hashFunc(element) % this.size;
      if (!this.bits[hash]) {
        return false; // Definitely not in the set
      }
    }
    return true; // Might be in the set
  }
  
  // Clear the filter
  clear() {
    this.bits.fill(false);
  }
  
  // Helper to create a Bloom filter with k hash functions
  static create(size, k) {
    // Create k hash functions using different seeds
    const hashFunctions = [];
    
    for (let i = 0; i < k; i++) {
      const seed = i + 1;
      hashFunctions.push(element => {
        let hash = 0;
        const str = String(element);
        
        for (let j = 0; j < str.length; j++) {
          hash = (hash * seed + str.charCodeAt(j)) & 0xffffffff;
        }
        
        return hash;
      });
    }
    
    return new BloomFilter(size, hashFunctions);
  }
}

// Usage example
const bloomFilter = BloomFilter.create(100, 3); // 100 bits, 3 hash functions

bloomFilter.add("apple");
bloomFilter.add("banana");
bloomFilter.add("orange");

console.log(bloomFilter.contains("apple")); // true
console.log(bloomFilter.contains("banana")); // true
console.log(bloomFilter.contains("grape")); // false (or true if false positive)

Applications​

  1. Spell checkers
  2. Cache filtering
  3. Network routing
  4. Database query optimization
  5. Duplicate elimination in data streams

Persistent Data Structures​

Concept and Purpose​

Persistent data structures preserve previous versions when modified, allowing access to all versions without full copying.

Implementation: Persistent Segment Tree​

class PersistentSegmentTree {
  constructor() {
    this.versions = [];
    this.init = null;
  }
  
  // Node structure for persistent segment tree
  createNode(left = null, right = null, value = 0) {
    return { left, right, value };
  }
  
  // Build initial version of the tree
  build(arr) {
    this.init = this._buildRecursive(0, arr.length - 1, arr);
    this.versions.push(this.init);
    return 0; // Return the version number
  }
  
  _buildRecursive(start, end, arr) {
    if (start === end) {
      return this.createNode(null, null, arr[start]);
    }
    
    const mid = Math.floor((start + end) / 2);
    const left = this._buildRecursive(start, mid, arr);
    const right = this._buildRecursive(mid + 1, end, arr);
    
    return this.createNode(left, right, left.value + right.value);
  }
  
  // Create a new version by updating a single element
  update(version, index, newValue, arrLength) {
    const newRoot = this._updateRecursive(this.versions[version], 0, arrLength - 1, index, newValue);
    this.versions.push(newRoot);
    return this.versions.length - 1; // Return the new version number
  }
  
  _updateRecursive(node, start, end, index, newValue) {
    if (start === end) {
      return this.createNode(null, null, newValue);
    }
    
    const mid = Math.floor((start + end) / 2);
    
    if (index <= mid) {
      const newLeft = this._updateRecursive(node.left, start, mid, index, newValue);
      return this.createNode(newLeft, node.right, newLeft.value + node.right.value);
    } else {
      const newRight = this._updateRecursive(node.right, mid + 1, end, index, newValue);
      return this.createNode(node.left, newRight, node.left.value + newRight.value);
    }
  }
  
  // Query the sum in range [l, r] for a specific version
  querySum(version, l, r, arrLength) {
    return this._querySumRecursive(this.versions[version], 0, arrLength - 1, l, r);
  }
  
  _querySumRecursive(node, start, end, l, r) {
    if (end < l || start > r) return 0;
    
    if (start >= l && end <= r) {
      return node.value;
    }
    
    const mid = Math.floor((start + end) / 2);
    const leftSum = this._querySumRecursive(node.left, start, mid, l, r);
    const rightSum = this._querySumRecursive(node.right, mid + 1, end, l, r);
    
    return leftSum + rightSum;
  }
}

// Usage example
const arr = [1, 2, 3, 4, 5];
const pst = new PersistentSegmentTree();

const v0 = pst.build(arr); // Initial version
console.log(pst.querySum(v0, 0, 4, arr.length)); // Sum of all elements: 15

const v1 = pst.update(v0, 2, 10, arr.length); // Change arr[2] from 3 to 10
console.log(pst.querySum(v1, 0, 4, arr.length)); // New sum: 22

// Original version is still available
console.log(pst.querySum(v0, 0, 4, arr.length)); // Still 15

Applications​

  1. Version control systems
  2. Functional programming data structures
  3. Undo functionality in applications
  4. Time travel debugging
  5. Concurrent access without locking

Conclusion: Choosing the Right Augmentation​

Augmenting data structures requires balancing:

  1. Time complexity of operations after augmentation
  2. Space complexity of the additional information stored
  3. Implementation complexity versus the benefits gained
  4. Maintenance overhead for future modifications

By strategically augmenting basic data structures, we can create powerful tools tailored to specific problem domains. As with all engineering decisions, the best choice depends on your particular use case, constraints, and performance requirements.

In the next articles, we'll explore more specialized data structures and techniques for solving complex algorithmic problems efficiently.