Bit vector with rank/select
N bits + o(N) overhead. rank(i) = # of 1s in [0, i]. select(k) = position of k-th 1. Both O(1).
Advertisement
LOUDS trees
Encode tree in 2N bits via 'level order unary degree sequence'. Nav in O(1).
Advertisement
BP trees
Balanced parentheses. Each subtree = matching pair. Find matching paren in O(1) with preprocessing.
FM-index
Compressed full-text index. Search substring in compressed text in O(P). Foundation of bioinformatics tools.