  We revisit the mergeable dictionaries with shift problem, where the goal is
to maintain a family of sets subject to search, split, merge, make-set, and
shift operations. The search, split, and make-set operations are the usual
well-known textbook operations. The merge operation merges two sets and the
shift operation adds or subtracts an integer from all elements in a set. Note
that unlike the join operation on standard balanced search tree structures,
such as AVL trees or 2-4 trees, the merge operation has no restriction on the
key space of the input sets and supports merging arbitrarily interleaved sets.
This problem is a key component in searching Lempel-Ziv compressed texts, in
the mergeable trees problem, and in the union-split-find problem.
  We present the first solution achieving O(log U) amortized time for all
operations, where {1, 2, ..., U} is the universe of the sets. This bound is
optimal when the size of the universe is polynomially bounded by the sum of the
sizes of the sets. Our solution is simple and based on a novel extension of
biased search trees.
