Last week, we explored a tradeoff between preprocessing time and query time. Today we explore a tradeoff between space usage, measured in bits, and time. We'll do so via an exploration of the binary ranking problem: given a bitvector $A\text,$ preprocess the bitvector to support queries of the form "how many 1 bits appear before a given index?"
Links