Skip to content
TheChatArchiveThe Chat Archive
Grok 4.1 Fast· xaiHugging Face Frontier Reasoning Traces

Implement a persistent segment tree to handle range queries.

  1. User

    Implement a persistent segment tree to handle range queries.

  2. Assistant
    class Node:
        def __init__(self, val=0, left=None, right=None):
            self.val = val
            self.left = left
            self.right = right
    
    class PersistentSegmentTree:
        def __init__(self, arr):
            """
            Initialize the persistent segment tree with the given array.
            Versions are stored in self.roots, where roots[0] is the initial version.
            """
            self.n = len(arr)
            self.roots = [self._build(arr, 0, self.n - 1)]
    
        def _build(self, arr, l, r):
            if l == r:
                return Node(arr[l])
            mid = (l + r) // 2
            left = self._build(arr, l, mid)
            right = self._build(arr, mid + 1, r)
            return Node(left.val + right.val, left, right)
    
        def update(self, version, pos, val):
            """
            Create a new version by updating position 'pos' (0-based) to 'val'.
            Returns the index of the new version.
            """
            new_root = self._update(self.roots[version], 0, self.n - 1, pos, val)
            self.roots.append(new_root)
            return len(self.roots) - 1
    
        def _update(self, root, l, r, pos, val):
            if l == r:
                return Node(val)
            mid = (l + r) // 2
            new_node = Node()
            if pos <= mid:
                new_left = self._update(root.left, l, mid, pos, val)
                new_node.left = new_left
                new_node.right = root.right
            else:
                new_right = self._update(root.right, mid + 1, r, pos, val)
                new_node.left = root.left
                new_node.right = new_right
            new_node.val = new_node.left.val + new_node.right.val
            return new_node
    
        def query(self, version, ql, qr):
            """
            Query the range sum from ql to qr (0-based, inclusive) on the given version.
            """
            return self._query(self.roots[version], 0, self.n - 1, ql, qr)
    
        def _query(self, root, l, r, ql, qr):
            if ql > r or qr < l:
                return 0
            if ql <= l and r <= qr:
                return root.val
            mid = (l + r) // 2
            left_sum = self._query(root.left, l, mid, ql, qr)
            right_sum = self._query(root.right, mid + 1, r, ql, qr)
            return left_sum + right_sum
    
    # Example usage:
    if __name__ == "__main__":
        arr = [1, 2, 3, 4, 5]
        pst = PersistentSegmentTree(arr)
    
        # Initial version 0: sum(0,4) = 15
        print(pst.query(0, 0, 4))  # Output: 15
    
        # Update version 0 at pos 2 to 10 -> new version 1
        v1 = pst.update(0, 2, 10)
        print(pst.query(1, 0, 4))  # Output: 20 (1+2+10+4+5)
        print(pst.query(0, 0, 4))  # Output: 15 (unchanged)
    
        # Another update on version 1 at pos 0 to 100 -> new version 2
        v2 = pst.update(1, 0, 100)
        print(pst.query(2, 0, 4))  # Output: 119 (100+2+10+4+5)
        print(pst.query(1, 1, 3))  # Output: 16 (2+10+4, unchanged from v1)
    

    This implementation provides a persistent segment tree for range sum queries.

    • Persistence: Each update creates a new root (version) without modifying previous versions. Versions are indexed starting from 0.
    • Time Complexity: O(log N) per update or query.
    • Space Complexity: O(N + Q * log N) where Q is the number of updates (each creates O(log N) new nodes).
    • Indices: 0-based for array positions and query ranges.
    • Supported Operations:
      • Initialize with array → version 0.
      • update(version, pos, val) → returns new version index.
      • query(version, left, right) → range sum.

    The example demonstrates persistence: old versions remain unchanged. You can extend it for min/max by changing the merge logic (e.g., min(left.val, right.val)). For dynamic nodes or other queries, modifications are straightforward.

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.