An immutable tree is often about as fast as a mutable tree, it's just pointer manipulation in either case.
An immutable data structure representing an array is definitely much slower than a mutable array (a contiguous piece of memory).
Usually != always, unfortunately :(