Generally the requirement for range queries and piercing queries. (Does range x,y contain object o; is object o overlapping range described by object p) Additionally requirement to maximize immutability for reasons of thread safety.

Range queries do not really work well on sorted vectors even if you have as many as needed indices. Immutability and race freedom are even more complex.

With a tree, copy on write solves many problems. (And can be much cheaper than copying whole structure.) If not, you can atomically replace subtrees in a safe way.