Something in between traditional bit vectors and sparse sets is described here: http://upcoder.com/9/fast-resettable-flag-vector/ http://upcoder.com/9/fast-res

Something in between traditional bit vectors and sparse sets is described here: http://upcoder.com/9/fast-resettable-flag-vector/ http://upcoder.com/9/fast-resettable-flag-vector/ This is designed for a fast clear, but doesn't actually have constant time clear, it's just O(n) clear with very small (amortized) constant. It's a bit more cache friendly, though, I think, and gave us some nice speedups in practice.