Grok 4.1 Fast· xai
Frontier Reasoning Traces
Implement a persistent segment tree to handle range queries.
- User
Implement a persistent segment tree to handle range queries.
- 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.
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.