I guess as soon as you have array mutation, you have assignment and thus it’s already imperative? The trick I’m thinking of definitely didn’t involve any algorithmic complexity overhead, it was just more of a trick to emulate assignment and imperative statements using pure functions. It was a neat observation at the time, but with the passage of time it starts to seem a little less surprising, though I guess it still is a little since the article asks the question.

Maybe you're thinking of the zipper data structure? [1]

Where you represent the composite structure hanging from the point you want to mutate, so updating that point is merely dropping the header and appending the updated value as a new prefix.

1 - https://en.m.wikipedia.org/wiki/Zipper_(data_structure)

No quite. By 'random access array' I meant changing an arbitrary array element, anywhere in memory.

Suppose you have array mutation, but the changes are only local.

Then as TuringTest pointed out, there are efficient ways to make those local changes in a functional programming language without the log(N) overhead.