TIL succinct data structures - data stored in a compact fashion as in a compression, but the compact form itself has useful properties.

The Rank/Select Bit Vector is a bit vector equipped with two fast operations - rank and select. The rank operator returns the number of set bits up to the n-th bit. The select operator returns the index of the n-th set bit, i.e. inverse of rank. The data structure has nice uses as in string lookup, etc.

The Wavelet Matrix is a generalization of rank/select bit vector on non-binary symbols. Another data structure of the class is the FM-index, whose operators extend to working on patterns (substrings) instead of symbols.