![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh1CKBUGD4hFiQXYpsnv4z2NXj_ApeeFYz1t8nyFv71ewO3cLthrL6IWOJ6ksiPuiQEvjB6N9r50Gy5WpPH4kVWewqK-pqbjrhLzOCyWvjn_-hdmJIDXe4NIH90Lr1f9l315aDIWEDJzmU8/s200/complexity_bitset.jpg)
The key intuition is to maintain two vectors such that dense[sparse[k]] = k, and a variable which maintains the number of elements in the sparse set. sparse[k] contains the number of elements in the set, when element k is inserted. In this way two elements inserted consecutively are mapped into contiguous positions of the dense vector. As a consequence, insert and delete operations are constant, while intersection and union operations are sub-linear.
This is the code for Sparse Sets representation in C++.
No comments:
Post a Comment