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.
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.
