Modern persistent tree-based data structures are usually O(log32n) random access, which is essentially O(1) for all practical purposes. With a mutable array of references, random access follows one pointer, while these structures follow usually less than 5. Sequential access is usually O(1).

These kind of persistent data structures are already the standard data structures in Scala and Clojure, and they are fast enough for the vast majority of non-numerical purposes. In typical access patterns, they are faster than mutable arrays.