“Immutable vectors are a convenient data structure for functional programming and part of the standard library of modern languages like Clojure and Scala. The common implementation is based on wide trees with a fixed number of children per node, which allows fast indexed lookup and update operations. In this paper we ex- tend the vector data type with a new underlying data structure, Re- laxed Radix Balanced Trees (RRB-Trees), and show how this struc- ture allows immutable vector concatenation, insert-at and splits in O(logN ) time while maintaining the index, update and iteration speeds of the original vector data structure.”