There is a vast array of data structures exploiting laziness and other tricks to achieve amortized constant time or even (for some limited cases, such as queues) constant time updates for many kinds of problems. Chris Okasaki’s PhD thesis “Purely Functional Data Structures” and book of the same name is a prime example (perhaps the first major one), but the field has advanced since. These data structures are typically not only purely functional in interface, but can also be implemented in pure Haskell and similar languages, and are fully persistent.

Even without any of these advanced tools, simple balanced binary search trees give logarithmic-time updates, so mutable memory can be simulated with at worst a logarithmic slow down.

There are other options, which may be considered cheating, but are very effective with regard to implementation effort and real-world performance. For example, linear types or uniqueness types allow in-place updating as implementation strategy for a conceptually pure language, by preventing the program from holding on to the previous value (the memory that would be mutated). This is less general than persistent data structures: For example, you can’t easily build an undo log by storing all previous versions of the state. It’s still a powerful tool, though AFAIK not yet available in the major functional languages.

Another option for safely introducing mutable state into a functional setting is the ST monad in Haskell. It can be implemented without mutation, and barring unsafe* functions, it behaves as if it was just a fancy wrapper around passing a persistent data structure implicitly (cf. State). But due to some type system trickery that enforces order of evaluation and prevents escaping, it can safely be implemented with in-place mutation, with all the performance benefits.

One cheap mutable structure is argument stack.

Take a look at the typical SICP-style factorial calculation:

(defn fac (n accum) 
    (if (= n 1) 
        accum 
        (fac (- n 1) (* accum n)))

(defn factorial (n) (fac n 1))

As you can see, the second argument to fac is used as a mutable accumulator to contain the fast-changing product n * (n-1) * (n-2) * .... There is no mutable variable is in sight, though, and there is no way to inadvertently alter the accumulator e.g. from another thread.

This is, of course, a limited example.

You can get immutable linked lists with cheap replacement of the head node (and by extension any part beginning from the head): you just make the new head point to the same next node as the old head did. This works well with many list-processing algorithms (anything fold-based).

You can get pretty good performance from associative arrays based e.g. on HAMTs. Logically you receive a new associative array with some key-value pair(s) changed. The implementation can share most of the common data between the old and the newly created objects. This is not O(1) though; usually you get something logarithmic, at least at worst case. Immutable trees, on the other hand, don’t usually suffer any performance penalty compared to mutable trees. Of course, this requires some memory overhead, usually far from prohibitive.

Another approach is based on the idea that if a tree falls in a forest and no one hears it, it needs not produce sound. That is, if you can prove that a bit of mutated state never ever leaves some local scope, you can mutate data within it safely.

Clojure has transients that are mutable ‘shadows’ of immutable data structures that don’t leak outside local scope. Clean uses Uniques to achieve something similar (if I remember correctly). Rust helps doing similar things with statically checked unique pointers.

What you’re asking is a bit too broad. O(1) removal and replacement from which position? The head of a sequence? The tail? An arbitrary position? The data structure to use depends on those details. That said, 2-3 Finger Trees seem like one of the most versatile persistent data structures out there:

We present 2-3 finger trees, a functional representation of persistent sequences
supporting access to the ends in amortized constant time, and concatenation and
splitting in time logarithmic in the size of the smaller piece.

(…)

Further, by defining the split operation in a general form, we obtain a general
purpose data structure that can serve as a sequence, priority queue, search tree,
priority search queue and more.

Generally persistent data structures have logarithmic performance when altering arbitrary positions. This may or may not be a problem, since the constant in an O(1) algorithm may be high, and the logarithmic slowdown might be “absorbed” into a slower overall algorithm.

More importantly, persistent data structures make reasoning about your program easier, and that should always be your default mode of operation. You should favor persistent data structures whenever possible, and only use a mutable data structure once you’ve profiled and determined that the persistent data structure is a performance bottleneck. Anything else is premature optimization.