Treaps can handle parallel set operations very efficiently:

https://www.cs.cmu.edu/~scandal/papers/treaps-spaa98.pdf

I don't understand how they differ in this regard from range trees, which they essentially are, just their method of construction is different.

Things like BSP trees are very good at intersections indeed, and have been used for things since time immemorial, but I think the skiplist/tree tradeoff is not that different in this domain.

Actually, prolly trees are probably best for intersections. You can use bloom filters as a first pass