For u32, the easy solution is to mmap enough space to hold a bitvector (4 billion/8b) then let sparse files do the rest for large (>32k entries) gaps. You'd the

For u32, the easy solution is to mmap enough space to hold a bitvector (4 billion/8b) then let sparse files do the rest for large (>32k entries) gaps. You'd then sum in wordlength blocks at k offset and popcnt. I'd be surprised if this wasn't the best behavior you could get trivially today. Depending on the processor you might win with SIMD or multithreading but you'd have to make the trade between them well unless you were really low on memory.