[consilient]

Lazy structures can usually get the log(n) back when you amortize over many operations.

[noctune]

Sure, but for some structures it amortizes to log(n) where mutable structures can amortize to O(1).