<think>.pdf

Immutable vectors are a key data structure in functional programming and modern languages like Clojure and Scala, typically implemented using wide trees with fixed children per node for efficient indexing and updates. Traditional implementations struggle with efficient vector concatenation, splits, and insert-at operations, which often require linear time. This paper introduces Relaxed Radix Balanced Trees (RRB-Trees) as an underlying structure for immutable vectors. RRB-Trees enable immutable vector concatenation, insert-at, and splits in O(log N) time while maintaining the original O(log₃₂N) index lookup and update performance. This improvement supports efficient parallel processing by allowing vectors to be split into partitions for concurrent evaluation, with results concatenated without linear copying. The design preserves cache efficiency and low constant factors from the original 32-way branching structure, making it suitable for languages like Scala, Clojure, C, and C++, and applicable to specialized use cases such as template-based web generation.