JCSS

Block Trees

We introduce a data structure, the block tree, that represents $S$ in $O(z \log(n/z))$ space and extracts any symbol of $S$ in time $O(\log(n/z))$, among other space-time tradeoffs. The structure also supports other queries that are useful for building compressed data structures on top of $S$.