SpanSet::intersectNot(SpanSet) uses nested for loops iterating over the two sets, O(N^2). It would be much more efficient (O(N)) to have a coordinated iteration (so long as the sets are sorted).
SpanSet::intersectNot(Mask<T>, T) currently creates a new SpanSet from the mask, and then creates another SpanSet with the overlap. I wonder if it would be more efficient to iterate over the mask with the span and create only one SpanSet result.
SpanSet::_runNormalize uses std::vector::erase, which is rarely a good idea.