Persistent Segment Tree — Time-Travel Queries

Node update(Node old, int start, int end, int idx, int val) {
  if (start == end) return new Node(val);
  int mid = (start + end) / 2;
  Node fresh = new Node(old);
  if (idx <= mid) fresh.left = update(old.left, start, mid, idx, val);
  else fresh.right = update(old.right, mid + 1, end, idx, val);
  fresh.sum = fresh.left.sum + fresh.right.sum;
  return fresh;
}